На 3 март 1862 г. вечерта напуска Карлово с коня на вуйчо си и отпътува за Пловдив, за да се сдобие с тескере. През София и Ниш се отправя към Белград, където се установява в началото на април. В столицата на Сърбия се включва в Първата българска легия на Георги Раковски в Белград. Запознава се отблизо с бунтовните среди на българската емиграция – Христо Иванов-Големия, Иван Кършовски, Васил Друмев и др. Заради своята ловкост и храброст по време на сраженията с турския гарнизон в Белград от 3 – 5 юни 1862 г. при Варош капия, Сръбска круна и Байраклъ джамия. получава името Левски (според легендата е направил „лъвски“ скок по време на военни упражнения в Сърбия). На този етап изпитва силно влияние от Георги Раковски и възприема идеята за организиране на чети, чрез които да се вдигне народът на въстание. В края на юни 1862 се присъединява и заедно с група легисти, е изпратен в Крагуевац, под ръководството на дядо Ильо войвода. Вместо военно обучение те трябвало да косят трева за сръбската армия, което довежда до конфликт с войводата им. Разтурването на легията през септември 1862 го заварва в Крагуевац, където слугува у богат сърбин. Заедно с Христо Големия заминава за Белград, където до края на 1862 учи абаджийство, а в свободното си време посещава казармата за усвояване на военни знания. В края на 1862 заминава за Влашко, където пребивава в столицата Букурещ до пролетта на 1863 (Според Васил Караиванов Левски заминава за Букурещ едва в ранната пролет на 1863 и не след дълго се завръща в България. ). През пролетта на 1863 се завръща в България и се установява като певец в църквата в Карлово. През лятото същата година е арестуван за три месеца в затвора в Пловдив (според някои източници – за участието му в легията, според друг – по оплакването на вуйчо му за кражбата на коня му). Според Васил Караиванов, и Левски, и вуйчо му, са арестувани в Пловдив, но само за месец. През зимата на 1863 и пролетта на 1864 г. живее в Пловдив и посещава за няколко месеца училището на Йоаким Груев. На 19 април 1864 г., навръх Великден, в местността Алтънчаир край Карлово, в присъствието на приятелите си хаджи Георги Попхристов и Христо Пулев, сам отрязва дългите си монашески коси. От този момент е мирски дякон (служител, помощник) на свободата Васил Левски. Архимандрит Василий се опитва да възбуди църковно следствие срещу племенника си, а пловдивският митрополит го заплашва с наказание ако упорства в настояването си.
От април 1864 до 1866 г. е учител в село Войнягово, Карловско, от март до октомври 1866 – в добруджанското Еникьой. Бидейки по-близо до границата, се надява да се свърже с Георги Раковски и да се запознае с неговите по-нататъшни планове. Като учител развива революционна пропаганда сред народа и организира патриотични дружини за бъдещото въстание. Посещава Тулча с надеждата да се срещне със Стефан Караджа, но не го открива. Там се запознава с поп Харитон, който по това време е свещеник там.[23]През октомври 1866 г. заминава за Влашко – за кратко е в Галац и Яш. Движи се в средите на Хаджи Димитър и Стефан Караджа. През ноември 1866 отново се среща с Георги Раковски. В края на 1866 и началото на 1867 е учител в с. Конгаз в Северна Добруджа. През март 1867 заминава за Букурещ, за да се включи в подготовката на революционната акция, замислена от Георги Раковски. По негово предложение е определен и включен като знаменосец в четата на Панайот Хитов, която се подготвя за прехвърляне в България. Заедно с четата изживява всички трудности и разочарования по време на нейния 99-дневен поход в Балкана (28 април-4 август). Заедно с четата преминава в Сърбия и известно време остава в гр. Княжевац. През август и септември 1867 г., заедно с Панайот Хитов и Иван Кършовски, живее в Белград, където постъпва във Втората българска легия (1867 – 1868).
Васил Левски (вляво), брат му Христо Кунчев и Христо Иванов – Големия по време на Втората българска легия в Белград, 1867 – 1868 г.
През февруари 1868 г. се разболява тежко (възпаление в коремната област налагащо операция която оставя дълго незаздравяваща рана), лежи във военна болница, където е опериран или в частна квартира според други източници. През април напуска Легията, която в края на месеца окончателно е разтурена от сръбското правителство. През май и юни 1868 е в Турну Мъгуреле, където заедно с Васил Ганчев-Плевнелията се уговарят да организират малка чета и да минат в България. През юни се среща с Хаджи Димитър в Букурещ във връзка с подготвяната чета, но не одобрява организацията им и се връща в Сърбия – в град Зайчар. В края на юни и юли за кратко е в затвора в Зайчар. За този престой той пише в писмо до Данаил Хр. Попов през 1871 г.: "...и аз на 68-о [лето] бяха затворен в Зайчар в тъмницата, защото съм бил проповядвал на тамошните българи да умират за българщината си, че им е отечество." През това време преосмисля изминатия път. През август е в Букурещ, където също е арестуван за кратко от влашките власти, заради минаването в България на четата на Хаджи Димитър и Стефан Караджа, но е освободен по здравословни причини – незарасналата рана от операцията в Белград, излекувана по-късно от Неофит Калчев. По това време съмненията му в целесъобразността на четническата тактика се превръщат в убеждение, че трябва да се търси нов път за постигане на крайната цел. За пръв път изразява мнение, че трябва предварителна подготовка на народа за участие в освободителното дело. В писмо до Панайот Хитов загатва за своите изводи и намерения, като му съобщава, че е решил да извърши нещо голямо в полза на отечеството:
„Но пак Ви моля и познавам за най-искрен и пръв любимец български, да дойдете при мен или да Ви пиша какво аз мисля да правя и ще го направя, ако рече Бог с Ваше позволение, ако го намерите благосклонно. И ще Ви моля да ми позволите, за което ако испечеля, печеля за цял народ, ако изгубя-губя само мене си“.
В него се засилва недоверието спрямо Сърбия и убеждението, че българите трябва да разчитат преди всичко на себе си, а не на външни сили. Гибелта на четата на Хаджи Димитър и Стефан Караджа окончателно го убеждава, че предварителната подготовка е необходимо условие за победата на българската революция. До декември 1868 г. живее в Букурещ, където се свързва с Иван Касабов и дейците на „Българското общество“. Към това време се отнася запознаването му с Христо Ботев и техният съвместен живот в една изоставена вятърна мелница край Букурещ. Единственият източник за съвместния живот на Левски и Ботев е цитирано от Захари Стоянов в писмо на Ботев до Киро Тулешков, чийто оригинал липсва. Това, а и пълното отсъствие на името на Ботев в запазената кореспонденция на Левски, дават основание на някои историци като проф. Иван Стоянов да твърдят, че вероятно те не са се срещали.