В Румынии потемкинцам отказали выдать снабжение, предложили сдаться и даже продать броненосец за 10 млн. франков. На это А. Н. Матюшенко ответил, что корабль принадлежит русскому народу и не продается. После такого ответа на помощь в Румынии рассчитывать уже не приходилось.
Снова встал вопрос: куда идти? Было несколько предложений: следовать в Одессу, в Керчь или в Евпаторию. Выбор пал на Феодосию, куда Потемкин и пришел 22 июня на 9-й день после восстания. В городе было мало пролетариата, но все-таки городское население встретило броненосец радостно, с сочувствием. По требованию Потемкина к борту подошел катер с представителями городских властей. Им сообщили, что экипаж Потемкина борется против самодержавия, в частности требует созыва Учредительного собрания. В заключение переговоров представителям города был вручен список снабжения, необходимого для броненосца: провизия, пресная вода и уголь. Представители городских властей обещали доставить все на корабль в 4 ч дня.
Обещание было выполнено лишь частично: на броненосец доставили провизию, пресную воду и сообщили, что начальник гарнизона запрещает выдать уголь для Потемкина.
Тогда в городскую управу был послан ультиматум следующего содержания: «Если завтра к 6 ч утра на корабль не будет доставлен уголь, в 10 ч броненосец открывает огонь по городу. Просим предупредить мирных жителей».
Между тем потемкинцы обнаружили в гавани три парусника, груженные углем. Решили захватить эти суда и перегрузить уголь на Потемкин. Однако когда моряки с броненосца поднялись на борт одного из судов и начали поднимать якорь, на берегу появилась рота солдат и открыла огонь. Действия военных властей объясняются просто: оказывается, с Потемкина в Феодосию сбежал матрос Кабарда, который на допросе сообщил, в какое трудное и опасное положение уже поставлен броненосец: нет припасов, угля, котлы в плохом состоянии, настроение у многих моряков подавленное. Аналогичную информацию жандармы получили и из перехваченных охранкой писем, которые некоторые потемкинцы попытались отправить своим родным из Феодосии. Матросы писали о своих трудностях, сомнениях и т. д. Военные власти Феодосии сделали вывод, что обстрел поможет вызвать на восставшем броненосце дезорганизацию и панику.
Когда на Потемкин доставили тела убитых товарищей, командой овладело негодование. Некоторые моряки в гневе предложили начать обстрел Феодосии. Но, как писал впоследствии А. Н. Матюшенко, «благоразумие и нежелание причинить вред невинным взяли верх над естественным гневом». И действительно, при артиллерийском обстреле города главной жертвой стал бы простой народ, свои братья — рабочие, солдаты. Броненосец снялся с якоря, и вскоре Феодосия скрылась за горизонтом. Потемкин шел в Румынию — сдаваться.
Оставалось совершить последний ритуал. Незадолго до похода к румынским берегам горнист протрубил сбор. Все свободные от вахт моряки выстроились на верхней палубе. Их глаза смотрели вверх, на грот-стеньгу, где все 11 дней восстания развевался сигнальный красный флаг, на котором были написаны слова: «Свобода, равенство и братство». Флаг революции решили похоронить в море. В полном молчании два матроса свернули флаг и опустили его в море. Он долго не тонул, покачиваясь на легкой зыби, и не отрываясь смотрели на него сотни пар глаз, потому что в эту минуту моряки прощались не просто с флагом — они прощались с революционным кораблем, с родиной.
В. И. Ленин впоследствии скажет: «... Броненосец «Потемкин» остался непобежденной территорией революции, и, какова бы ни была его судьба, перед нами налицо несомненный и знаменательнейший факт: попытка образования ядра революционной армии.» (В. И. Ленин. Полн. собр. соч. Изд. 5-е, т. 10, с. 337.)
25 июня корабль прибыл в Констанцу. Румынский король прислал на Потемкин телеграмму с гарантией обеспечить неприкосновенность русским морякам. Нарушить свое слово он не решился: в то время в Румынии сильным влиянием пользовалась партия социалистов, предательство по отношению к потемкинцам могло привести к волнениям в Румынии. Передав Потемкин румынским властям, моряки беспрепятственно сошли на берег как политические эмигранты.
По-разному сложились судьбы моряков с Потемкина: одни стали бедствовать в Румынии, работая батраками и чернорабочими, другие разъехались по разным странам. Часть матросов поверила царскому манифесту 1905 г. и вернулась на родину, все они были сосланы на каторгу и получили свободу только в 1917 г.
Один из главных руководителей восстания на Потемкине А. Н. Матюшенко в 1907 г. вернулся в Россию под чужим именем, но был опознан провокатором и после суда повешен.