Создан к 45-летней годовщине погребения в городском соборе основателя Херсона, князя Потёмкина, по модели, изваянной в 1831 г. академиком И. П. Мартосом. В конце 1836 г. занял своё место в центре города. Автором массивного гранитного пьедестала стал итальянский архитектор ФранцКарлович Боффо, в 1820—1830-х годах много работавший в Одессе и выполнивший пьедестал к памятнику Ришельё работы того же Мартоса. В 1840 году вокруг памятника был высажен бульвар, названный Потемкинским и обнесённый оградой.
После прихода к власти большевиков (1917 год) памятник Потемкину был закрыт брезентом, из-за чего в народе получил прозвище «херсонский призрак»[2]. в 1927 году его сняли с постамента (27.04.1927) и перенесли во двор Херсонского историко-археологического музея. В 1944 году, когда Херсон освободили советские войска, памятника не обнаружили. В 2003 году к празднованию 225-летия города он был восстановлен херсонским скульптором Юриком Степаняном.
В октябре 2022 года вместе с несколькими другими памятниками, а также прахом Потёмкина, был вывезен из Херсона.[3]