Родственники Потемкина не забыли то место в степи, которое отметил своей пикой казак Головатый. В 1792 году Самойлов поставил здесь классической формы обелиск с высеченными на гранях надписями. Рисунок обелиска и белый камень, из которого он сделан, так напоминают фонтан в Николаевском дворце, что, скорее всего, проект стелы принадлежал тому же архитектору — Ивану Старову. Позднее, в начале XIX века, наследники Потемкина поставили рядом с обелиском пирамиду десятиметровой высоты из темного камня.

В Херсоне тело Потемкина было положено в раку в центре церкви св. Екатерины-великомученицы. Императрица заказала мраморное надгробие, но через пять лет, когда она умерла, плита еще не была готова. Потемкин оставался не похороненным. У раки светлейшего молились местные жители и приезжие; в их числе был и Суворов.

Об этих посещениях узнал Павел I и страшно разгневался: даже через семь лет после своей смерти Потемкин продолжал нарушать традиции и приличия. 18 апреля 1798 года император подписал приказ генерал-прокурору Александру Куракину, «дабы все тело без дальнейшей огласки в самом же том погребу погребено было в особо вырытую яму, а погреб засыпан землею и выглажен так, как бы его никогда не бывало». Предание гласит, что на словах император приказал Куракину не только уничтожить все, что напоминало о Потемкине, но и разбросать его кости по Чертову ущелью невдалеке от церкви. Могила была выкопана и снова зарыта под покровом ночи.

4 июля 1818 года архиепископ Екатеринославский Иов Потемкин, кузен светлейшего, распорядился снять плиту пола в церкви св. Екатерины и поднять гроб. Набальзамированное тело оказалось на месте — как это случалось не раз, подданные игнорировали безумный каприз Павла. Говорили, что, уезжая из Херсона, Иов что-то увез с собой. Была ли это урна с частью праха Потемкина?

По воцарении Александра I Потемкин был реабилитирован. Было решено поставить памятник Потемкину в Херсоне. Проект заказали И.П. Мартосу, но скоро работа остановилась из-за очередной ссоры наследников о деньгах — памятник стоил 170 тысяч рублей — и возобновилась только в 1826г. Колоссальный бронзовый монумент, открытый в 1837г., представлял Потемкина в римских доспехах, с мечом, в шлеме с плюмажем, на высоком пьедестале. Во время гражданской войны власть в Херсоне менялась несколько раз, и петлюровцы, мстя за ликвидацию Запорожской Сечи, сняли памятник с пьедестала и поставили во двор местного музея. Во время Второй Мировой войны памятник был то ли вывезен, то ли уничтожен немцами.

Каждое новое вскрытие могилы рождало новые сомнения. В 1859 году еще одна официальная комиссия убедилась, что тело князя на месте. Под полом обнаружили большой склеп, в нем деревянный гроб, в деревянном — наглухо запаянный свинцовый. Местный чиновник Ф. Мильгоф осмотрел склеп и приказал запечатать его снова.

Решено было возвести надгробие — но выяснилось, что никто не заметил точного места, где его надо поместить. В 1873 году очередная комиссия вскрыла захоронение и нашла части свинцового и деревянного гробов, куски золотого позумента и три орденские звезды, а также маленький деревянный ящик, содержащий череп с треугольным отверстием в основании — вероятно, тем, что сделал доктор Массо при бальзамировании, — и остатки каштановых волос. На этот раз над могилой поставили надгробную плиту. Прах Потемкина, если это был он, наконец обрел покой.

Затем произошла революция. Большевики приказали раскопать кладбище при церкви св.