Происхождением фразеологизм обязан историческому факту путешествия русской императрицы Екатерины Второй в Крым в 1787 году, во время которого главный организатор поездки и одновременно Екатеринославский, Таврический и Харьковский Генерал-Губернатор граф Г. А. Потемкин якобы представил Екатерине несуществующие достижения в освоении края как то: бутафорские селения, склады хлеба, где в мешках вместо муки был песок, тучные стада, ради чего одно и то же стадо, перегонялось по ночам с места на место, крепость в Херсоне, развалившаяся после первой грозы и т. п. Было ли так на самом деле, историки спорят до сих пор.
Одни утверждают, что рассказы о недобросовестности Потемкина («Потемкинских деревнях») — злопыхательства его многочисленных врагов и завистников как в окружении Екатерины, так и в среде европейских дипломатов, сопровождавших императрицу в поездке. Другие приводят свидетельства участников поездки — австрийского императора Иосифа Второго, участвовавшего в путешествии инкогнито под именем граф Фалькенштейна, французского дипломата Сегюра.
Правда, скорее всего, как обычно, по середине. Потемкину, конечно, хотелось представить себя и всё сделанное им в Новороссии самым лучшим образом. В этом нет ничего зазорного. Европейцы, для которых успехи России на юге были мало приятны, чтобы успехи эти нивелировать, могли кое-что приврать или приукрасить. Екатерина тоже не просто так пригласила с собой в поездку иностранцев. Надеялась показать им и своё могущество, и возросшую мощь возглавляемой ею державы. То есть, театр, устроенный Потемкиным, предназначался вовсе не ей, а её гостям, она же, как женщина умная, всё прекрасно видела, знала и, вполне возможно, была с Потемкиным в сговоре.
Так ли, иначе, но путешественников в Крым что русских, что европейских «Потемкинскими деревнями» провести не удалось. Секретарь саксонского посольства при дворе Екатерины II Георг-Адольф Вильгельм фон Гельбиг, живший в Петербурге с 1787 по 1795 годы, но в поездке не участвовавший, собрал ходившие о ней в столице слухи и сплетни и в 1809 в Гамбурге тиснул книгу, содержащую 110 биографий известных русских людей, в том числе и графа Потемкина. В России книга сразу же получила известность, благодаря литературным журналам, перепечатывавшим из неё отрывки, но полностью, хотя и со множеством купюр по цензурным соображениям, появилась в России в 1887 году под заглавием «Русские избранники и случайные люди». Только в 1900 году в Германии была издана по-русски полностью. Гельбик и считается опосредствованным автором фразеологизма «Потемкинская деревня», но имя настоящего автора история не сохранила.