Потёмкинская улица с конца XVIII века соединяла Кирочную и Шпалерную улицы. Первоначально она называлась Артиллерийской Поперечной. В 1780-х годах неподалёку для графа Г. А. Потёмкина был построен Таврический дворец, при нём был разбит сад. Чётная сторона улицы стала граничить с Таврическим садом.
В 1800-х годах по проекту Л. Руска был построен Манеж Кавалергардского полка (дом №1). С начала XIX века до 1870-х годов улица называлась Таврической. Современная Таврическая в то время именовалась Садовой. В 1870 годах улица стала называться Потёмкинской, что связано с фамилией князя Г. А. Потёмкина.
В 1903-1906 годах был построен дом №9 - особняк С. С. Боткина.
В конце 1950-х годов был открыт киноцентр "Ленинград" (дом №4). В 1983 году дом №46 по Шпалерной (тогда Воинова) улице был снесён, Потёмкинская улица получила выход к набережной Невы.
