В апреле последовал новый приказ, о котором генерал-прокурор писал новороссийскому губернатору И. Я. Селецкому: «Известно государю императору, что тело покойного князя Потемкина доныне еще не предано земле, а держится на поверхности в особом сделанном под церковью погребу и от людей бывает посещаемо. А потому, находя сие непристойным, высочайше соизволяет, дабы все тело без дальнейшей огласки в самом же том погребу погребено было в особо вырытую яму, а погреб засыпан землею и изглажен так, как бы его никогда не бывало». На основании «Записок» Ланжерона считается, что комендант Херсона полковник Тернер отрапортовал в столицу об исполнении приказа, а сам велел солдатам просто засыпать склеп землей. Эти события породили среди жителей слухи, будто тело светлейшего князя перезахоронили на городском кладбище или даже зарыли во рву крепости.

При Павле имя Потемкина не произносилось. По южным землям прокатилась волна переименований: Таврида снова, как во времена ханства, стала Крымом, Севастополь превратился в Ахтияр, Керчь — в Еникале. Все военные мероприятия князя были отменены. Оставшиеся в живых сослуживцы светлейшего подверглись опале. Попов был сослан в имение, Секретарев — в Оренбург, Гарновский посажен в крепость.

Уже в царствование Александра I в 1818 году херсонский архиепископ Иов решил убедиться в целости захоронения. В ночь на 4 июля он с несколькими духовными лицами поднял церковный пол, проломил свод склепа, вскрыл гроб и, по его словам, обнаружил тело на месте. В 1859 году, уже после Крымской войны, власти Херсона предприняли еще одно исследование гроба. Оказалось, что доски его разваливаются, раздавленные землей, которой когда-то столь тщательно засыпали склеп. Пяти спустившимся в подвал лицам удалось откопать череп и несколько костей, которые они положили в железный ящик с задвижкой и оставили в склепе. Стоит ли говорить, что каждое такое «посещение» порождало волну слухов. В 1874 году Одесское общество истории и древностей вознамерилось поставить точку в эпопее обследований могилы Потемкина. Научная комиссия во главе с Николаем Мурзакевичем 19 августа вновь потревожила покой светлейшего князя. Был найден железный ящик с черепом и несколькими костями, а затем обследован сам склеп. В нем обнаружены фрагменты деревянного и свинцового гробов, куски золотого позумента, серебряные гробовые скобы и три шитые канителью орденские звезды 1-й степени: Святого Андрея, Святого Георгия и Святого Владимира.

Это описание показывает, что когда-то склеп все-таки был разорен, раз от дорогих гробов остались одни детали, от богатого мундира — лишь позумент да канитель, а от тела — череп и всего несколько костей. Куда девалось остальное? Результаты обследования одесского исторического общества позволяют сомневаться как в рассказе Ланжерона, так и в сообщении Иова о целости захоронения. Вероятно, месть Павла все же была осуществлена.

После всех этих перипетий с могилой, когда большинство жителей Тавриды были уверены, будто тело Потемкина вообще выкинуто из гроба и зарыто неизвестно где, что же оставалось памятником светлейшему князю? Державин дает ответ:

Памятником Потемкину были построенные им города, покоренные вражеские твердыни и сильный Черноморский флот.

18 августа 1801 года, вскоре после смерти Павла I, Самойлов обратился к Александру I с просьбой разрешить родным князя построить в Херсоне монумент. Молодой император подписал соответствующий манифест, но дело не стронулось с места, потому что наследники баснословного состояния не смогли выделить нужную сумму. В 1825 году новый генерал-губернатор Новороссии граф Михаил Семенович Воронцов повторил государю просьбу жителей о сооружении «в Херсоне памятника основателю Новороссийского края покойному светлейшему князю Потемкину-Таврическому». У деятельного Воронцова уже имелись эскизы, выполненные И.