Петко наистина заминава за Македония и в продължение на два и половина месеца броди от село на село, от град на град, за да се върне изморен, отегчен и мразен. Революционният барут на македонците ще се възпламени едва след 20– 30 години. По това време, когато Петко броди из Македония, огнивото, което ще подпали този барут, е още мокро от неизплаканите сълзи и всичките усилия на Петко да го изсуши със силни и горещи думи са напразни, защото всяко нещо, както хиляди пъти е потвърдила нашата учителка — историята, идва със своето време.
След завръщането си от несполучливата си мисия в Македония Петко решава да „зареже гръцките ласкателства“, както самият той се изразява в своите спомени, и да замине при Гарибалди в Италия. Трябва да се каже, че звездата на този легендарен патриот и мъж свети по това време в пълния си блясък и привлича много поклонници на неговата слава от всички краища на света. Гарибалди не е само едно прославено име, но това име е по онова време символ на свободата и всеки, който й служи и желае да се жертвува за нея, смята, че трябва да отиде при Гарибалди, да види Гарибалди, да говори с Гарибалди, да научи от Гарибалди тайната на революционния успех. Петко заминава, среща се с Гарибалди, който го задържа при себе си и за известно време младият български войвода е постоянен гост на прочутия революционер. От него нашият Петко Кирков или „Киряков“, както се подписва той по същото време, научава много неща за революционната стратегия и тактика и за хайдушкия морал. Между другото под влиянието на Гарибалди той изживява в себе си илюзиите на старото хайдутство като изолиран бунт, свързан само с личното отмъщение, и си поставя високата цел — освобождаването на своя поробен народ.
Петковото гостуване у Гарибалди не минава само в поучения и голи приказки, а се увенчава и с дела. С помощта на всесилния италианец се сформира една дружина от 220 души италиански патриоти, която под началството на един от сподвижниците на Гарибалди — Фридрих и Петко заминава през Атина за Крит, където през 1866 г. пролетта избухва противотурското Критско въстание. Увеличена,в Атина още с около 70 души доброволци, Гарибалдиевата дружина минава под командата на Коронел, а Петко получава един по-малък самостоятелен отряд в планината Щили. — доверие, което младият предводител напълно оправдава в ожесточените сражения с турците. Битките следват една след друга: на 30 март, — на 6 май, на 20 май, на 10 юни, на 1 август — все кръвопролития, с един противник многочислен, храбър и отлично въоръжен, затова успехите, които печели Петко в тези битки, прославят неговото име като на един от най-безстрашните борци и му спечелват прозвището „Капитан“.
За съжаление историята на Критското въстание е свързана не само с победи и геройства, но и с големи раздори между ръководителите за властта, което отслабва въстанието, и през 1868 година започват преговори за примирие. Според условията на това примирие, което се подписва от Коронел, въстаниците трябва да минат обезоръжени между две редици турски войници като един вид „евалла“, самопризнание за превъзходството на турската сила. Всички се подчиняват на примирието, единствен българинът Капитан Петко, както ще се нарича той отсега нататък, отказва да изпълни това унизително условие и заедно с 18 души въстаници заминава с един кораб за Александрия.
Два месеца празно скитане из кафенетата и пазарищата на шумния египетски град са достатъчни за младия капитан да разбере, че неговото място не е в този разпален от жежкото слънце и развонял се на банани източен град и той решава да замине за Марсилия. Какво е смятал да прави там нашият хайдутин и като какъв му се е сторил този френски град, нямаме за съжаление никакви данни. Едно е само известно, че след шестмесечен престой в Марсилия Петко се качва на една гемия и се завръща пак в Атина, отракан, понаучил френски и отегчен до смърт от дългата насилствена почивка. По време на тази почивка той е премислил много неща и е скроил какво да прави, тъй че още със завръщането си в Атина през пролетта на 1869 година започва да издирва бивши участници от Критското въстание и да събира около себе си по-юначните българи, за да сформира една дружина, но не вече хайдушка, а въстаническа, която ще върви да се бие за освобождението на Гракия.