Чтобы пополнить запасы угля, пресной воды и продовольствия, комиссия решила зайти в порт Феодосию. В принципе решение это было разумным — там не имелось береговой артиллерии и военных кораблей, зато было много угля и коммерческих судов.
Около 7 часов утра 22 июня «Потемкин» и миноносец № 267 бросили якоря на рейде Феодосии. Население города бурно приветствовало восставших. На борту броненосца побывали члены городской управы, которые выразили сочувствие матросам. Управа к 16 часам доставила на «Потемкин» четырех живых быков, крупу, муку, кур, зелень. Однако военные власти не допустили доставки на корабли угля.
На вторые сутки пребывания в Феодосии потемкинцы договорились с владельцами двух шхун, груженных углем. Однако при попытке буксировки парусных шхун паровым катером и миноносцем восставшие были обстреляны винтовочным огнем роты солдат. В ходе обычной войны командир роты, решивший воевать винтовками против 12-дюймовых орудий броненосца, был бы сочтен слабоумным. Я уж не говорю о том, что на миноносце № 267 имелись две 37-мм пушки Гочкиса, да и на катере должна была стоять одна такая 37-мм или 47-мм пушка. Но матросов вновь охватила паника, а проворный Алексеев вновь отдал приказ сниматься с якоря.
В ночь на 26 июня «Потемкин» и миноносец № 267 вернулись в Конетанцу и стали на якоря в полумиле от порта. Румынские власти гарантировали восставшим свободу и невыдачу царским властям. На броненосце спустили красный флаг и подняли флаг королевского флота. Вскоре в порт явился русский консул и стал уговаривать матросов вернуться в империю. Команда миноносца № 267 поверила и увела корабль в Севастополь. Прапорщик Алексеев, кондуктора «Потемкина» и несколько новобранцев, всего около тридцати человек, также решили возвратиться в Россию.
А между тем адмирал Чухнин в Севастополе развил бурную деятельность по поимке мятежного броненосца. По его приказу с эсминца «Стремительный» был списан весь экипаж, за исключением трюмной команды из 9 человек[7]. Взамен эсминец был укомплектован офицерами с разных судов. «Стремительный» (скорость 28 узлов) стремительно гонялся за «Потемкиным» (скорость 16 узлов, но на самом деле не более 13 узлов), но никак не мог поймать броненосец. Командир «Стремительного» А.А. Янович во время стоянки в Ялтинском порту получил телеграмму, что «Потемкин» пришел в Феодосию. В 130 км от Ялты, в Феодосии, броненосец простоял почти полтора суток. «Стремительному» туда было 2,5 часа полного хода. Но храбрый Янович ухитрился разминуться с «Потемкиным».
Помимо «Стремительного» торпедировать «Потемкин» пожелал и командир минного крейсера «Гридень». Крейсер вышел из Севастополя, но в пути бравый командир узнал, что матросы тоже готовятся к встрече с броненосцем, но совсем с иными намерениями. «Гридень» немедленно повернул назад и вернулся в главную базу.
Между тем 18 июня на переходе Николаев — Севастополь революционные матросы захватили учебное судно «Прут» (водоизмещение 5459 т, скорость 13,5 узла, вооружение: восемь 47-мм и две 37-мм пушки). В ходе захвата были убиты вахтенный офицер и боцман, а командир и старпом арестованы. Восставшие повели судно в Одессу к «Потемкину». Однако броненосца там не оказалось, и матросы решили идти в Севастополь поднимать восстание. Но что легко могли сделать «Потемкин» с «Георгием», было не по силам тихоходному судну с десятью пушечками Гочкиса. У входа в Севастопольскую бухту «Прут» перехватили два эсминца и привели в базу, где вся команда была арестована.
Узнав об уходе «Потемкина», эскадра под командованием Вишневецкого сходила к Одессе и легко сняла с мели «Георгия», который практически не имел повреждений и был немедленно введен в строй с частично замененной командой. Эскадра вместе с «Георгием» вернулась в Севастополь.
23 июня на поиски «Потемкина» выходит эскадра в составе «Ростислава», «Георгия Победоносца», «Трех Святителей», «Двенадцати Апостолов», минного крейсера «Казарского» и четырех эсминцев. Но увы, эскадра так и не может или не хочет изловить мятежников.
Но вот в 10 часов утра 16 июня броненосцы «Чесма» и «Синоп» в сопровождении миноносцев №№ 261, 262, 264 и 265 настигли «Потемкин». Но к великому огорчению адмирала Писаревского, на нем развевался румынский флаг, а революционные матросы давным-давно сошли на берег и стали политическими эмигрантами.
Днем 28 июня «Потемкин» на буксире броненосца «Синоп» был выведен из порта Констанцы и рано утро 1 июля прибыл в Севастополь.