Осенью 1864 года Петко-воевода приехал в Афины и стал курсантом Военного училища. В июле 1865 года Афинский революционный комитет, решив, что Петко уже получил достаточную военную подготовку, поручил ему весьма деликатную миссию в Македонии. Ему предстояло объехать те края и организовать там восстание, которое отвлекло бы внимание турок от восстания, готовящегося на Крите.
Петко и впрямь отправился в Македонию, два с половиной месяца ходил из села в село, из города в город и возвратился в Афины измученный, расстроенный, а главное, без всякого результата. Нужны были еще долгие годы, не менее двух-трех десятков лет, чтобы в Македонии вспыхнул революционный порох. А в те годы огниво, которому предстояло поджечь этот порох, было еще сырым от невыплаканных слез, и все усилия Петко высушить его жарким и сильным словом оказались напрасными, ибо, как это тысячу раз доказано нашей наставницей-историей, всему на свете свой черед.
После возвращения из неудачной своей поездки Петко решил «отказаться от греческих милостей», как сам он выразился в своих воспоминаниях, и уехать в Италию, к Гарибальди. Надо сказать, что звезда этого легендарного итальянского патриота сверкала в ту пору полным блеском и привлекала к себе бесчисленных поклонников со всех концов земли. В ту пору Гарибальди — не только громкое имя, а символ свободы, и каждый, кто служил ей и жаждал отдать за нее жизнь, считал своим долгом побывать у Гарибальди, увидеть его, говорить с ним, узнать у него тайну революционного успеха. И Петко тоже поехал, встретился с Гарибальди, а тот оставил молодого болгарина у себя, и некоторое время воевода был постоянным гостем прославленного революционера, учился у него революционной стратегии и тактике, нормам гайдуцкой морали. Между прочим, именно под влиянием Гарибальди Петко избавился от многих заблуждений гайдуков прежних времен, действовавших изолированно и имевших целью лишь личную месть, и поставил перед собой высокую цель — освобождение своего порабощенного народа.
Пребывание Петко-воеводы в Италии проходило не только в поучениях и разговорах, оно было увенчано делом. С помощью всесильного в ту пору Гарибальди был создан отряд итальянских патриотов, численностью в 220 человек, под командованием друга Гарибальди, Фридриха, и в составе этого отряда Петко через Афины отправился на Крит, где весной 1866 года вспыхнуло восстание против владычества турок. В Афинах гарибальдийский отряд, выросший еще человек на семьдесят, поступил под командование Паноса Коронеаса, а Петко возглавил другой отряд, поменьше — доверие, которое молодой полководец вскоре полностью оправдал в ожесточенных схватках с турками. Сражения следуют одно за другим: 30 марта, 6 мая, 20 мая, 10 июня, 1 августа — кровопролитные битвы с многочисленным, храбрым и хорошо вооруженным противником, поэтому победы, одержанные Петко в этих сражениях, принесли ему славу одного из храбрейшего военачальников и прозвище Капитана (так на Крите называли командиров повстанческих отрядов).
К сожалению, в истории Критского восстания были не только победы и героические подвиги, но и серьезные раздоры между его руководителями. Это ослабляло силы повстанцев, и в 1868 году им пришлось начать переговоры о перемирии. По условиям перемирия, подписанного Коронеасом, обезоруженные повстанцы должны были пройти между двумя шеренгами турецких солдат в знак признания турецкой силы, ее превосходства. Все подчинились этому унизительному условию, все, кроме Капитана Петко, как его стали с тех пор называть. Вместе с 18 повстанцами он сел на корабль и отплыл в Александрию.
Два месяца праздных шатаний по кофейням и базарам оказались достаточными для того, чтобы юный воевода понял, что ему не место в этом распаренном солнцем и пропахшем бананами шумном восточном городе. Он решает уехать в Марсель. Каковы были его планы, чем думал он там заняться, каким представлялся ему этот французский город — на этот счет, мы, к сожалению, не располагаем никакими сведениями. Известно лишь, что после полугодового пребывания в Марселе Петко вновь возвратился в Афины, пообтесавшийся, поднаторевший во французском языке и полный лютой тоски от столь длительного вынужденного отдыха. За это время он о многом поразмыслил и обдумал свои планы на будущее, так что сразу же по приезде в Афины весной 1869 г. он принялся разыскивать уцелевших участников Критского восстания и формировать отряд, уже не гайдуцкий, а повстанческий, чтобы сражаться за освобождение Фракии.