В 1787 году Екатерина вместе со своим двором, прихватив с собой иностранных дипломатов, совершила свой знаменитый вояж по новым владениям. Путь их лежал через Новороссию. С этой поездкой связано предание о «потемкинских деревнях». Рассказывали, что Потемкин, чтобы скрыть свои злоупотребления и казнокрадство и чтобы уверить гостей, что его губерния процветает, выставлял на пути кортежа бутафорские деревни, где «пейзане», а точнее, нанятые актеры изображали довольство и счастье и с восторгом встречали императрицу и ее спутников. Поскольку участники путешествия не оставили никаких записей о своих впечатлениях от Новороссии, мы не можем знать, на самом ли деле они посещали эти «невзаправдашние деревни». Известно только, что такого рода «маскарады» были очень популярны в XVIII веке (вспомним описание свадьбы Анны Леопольдовны), но… гости прекрасно знали, что это игра, инсценировка, и никто не пытался убедить их в том, что они находятся в настоящей деревне и встречаются с настоящими крестьянами. Биограф Потемкина граф Самойлов возмущался: «Что деятельность Потемкина была крайне неприятно иностранцам, это вполне понятно. Господствуя у нас печатным словом, иноземцы распространили мнение (которое и доселе не совсем уничтожено), будто все эти работы были каким-то торжеством обмана, будто Потемкин попусту бросал деньги и показывал государыне живые картины, вместо настоящих городов и сел». Но позже энциклопедический словарь Брокгауза и Эфрона писал: «В 1787 году предпринято было знаменитое путешествие императрицы Екатерины на юг, которое обратилось в торжество Потемкина, с замечательным искусством сумевшего скрыть все слабые стороны действительности и выставить на вид блестящие свои успехи».
Императрица осмотрела построенный Потемкиным Херсон, ночевала в ханском дворце в Бахчисарае, наблюдала за маневрами флота в Севастопольской бухте. Она написала: «Я всем обязана князю Потемкину. Надеюсь, теперь никто не назовет его ленивым». В том же году Потемкин получил почетный титул князя Таврического.
Хотя они расстались (точнее, это Екатерина оставила его), но все же расстались друзьями и продолжали ими оставаться. Недаром императрица писала Потемкину: «А твои собственные чувства и мысли тем наипаче милы мне, что я тебя и службу твою, исходящую от чистого усердия, всегда люблю, и сам ты бесценной».
Если Екатерина и Потемкин действительно тайно стали мужем и женой, то это случилось где-то между весной 1774-го и зимой 1775 года. Мемуаристы называют разные даты и разные церкви, где они венчались: то ли это случилось «в церкви Сампсония, что на Выборгской стороне», то ли в имении Екатерины Пелла, то ли в Храме Вознесения Господня в Сторожах, у Никитских ворот.
Если наша героиня действительно была дочерью этой пары, то она появилась на свет в июле 1775 года, когда в Москве как раз праздновали заключение Кючук-Кайнар-джийского договора, но праздновали… без Екатерины. Императрица была больна и не выходила (по официальной версии, у нее было кишечное расстройство). Однако большинство историков сомневается в этом. Дело в том, что Екатерина, одержимая страстью «все устраивать», не забывала своих детей, пусть даже незаконнорожденных. Со своим сыном от Григория Орлова, Алексеем Бобринским, она поддерживала связь: писала ему письма, оплачивала его долги, журила, потом, убедившись в полной его безалаберности, оставила жить в провинции, в Ревеле, но разрешила приехать ненадолго в Петербург после женитьбы, чтобы познакомиться с его избранницей, Анной Унгерн-Штернберг, дочерью барона Вольдемара Унгерн-Штернберга, коменданта ревельской крепости. А к судьбе девочки она ни разу не выказывала никакого интереса. Встречался с Бобринским и Павел уже после смерти Екатерины. Но он никогда не вспоминал о своей предполагаемой сестре.
Зато Потемкин сразу признал малышку и дал ей, как это тогда было принято, свою урезанную фамилию — Темкина. Елизавету Темкину воспитывала сестра Григория, Мария Александровна Самойлова, а опекуном девочки назначили его племянника Александра Николаевича Самойлова.