Территория по которой проходит Фурштатская улица относится к одному из самых первых регулярно застроенных районов Санкт-Петербурга. По плану архитектора Доменико Трезини 1712 года от Литейной улицы вдоль Невы был проложен ряд улиц-линий. Между Невой и северной стороной будущей Кирочной улицы расположилась Пушкарская (Артиллерийская) слобода, частью которой Фурштатская улица и стала.
Первоначально улицы здесь назывались по номерам. С 1720-х по 1777 год Фурштатская улица называлась "4-я от Невы реки линия". До 1799 года - 3-я Артиллерийская улица. Далее - Фурштатская. Это название связано с "фурштатом", полковым обозом Преображенского полка. Двор полкового обоза располагался на участке современных домов №21 по Фурштатской улице и №20 на Кирочной улице. С XIX века в обиходе существовало и преобразованное название - ФурштаДтская улица. Так её упоминали не только в разговоре, но и в официальных документах, на указателях с номерами домов.
В 1775-1779 годах построена лютеранская церковь Святой Анны. С 1790-х годов на участке дома №26 находился полицейский дом Литейной части.
С самого начала истории района участки по Фурштатской улице выдавались в основном военным, чиновникам, служителям дворцового ведомства. До середины XIX века улица была застроена в основном каменными одно- и двухэтажными домами. Только с 1850-х годов здесь началась массовая застройка 4- и 5-этажными зданиями.
В 1840-х годах построено здание для полкового обоза Преображенского полка (дом №21). В 1820-1840-х годах участком дома №42 владел правнук последнего грузинского царя князь Иоанн Григорьевич грузинский.
В 1852 году проходила продажа земельных участков, оставшихся после расформирования Артиллерийского госпиталя. Тогда были проданы участки домов №31, 33, 35 и 37. В 1856 году для купца Кононова построен дом №33, с тех пор он не перестраивался. В 1859-1860 годах по проекту Роберта Андреевича Гедике был построен дом №23.
В середине XIX века при постройке церкви святых Космы и Дамиана за его зданием между Фурштатской и Кирочной улицами был проложен безымянный переулок. В 1887 году он стал называться Козмодемьянским.
В 1864 году Фурштатский двор был расформирован, участок поделён на двое. Половина со стороны Фурштатской улицы стала принадлежать Петербургскому Арсеналу.
В 1865 году для графа В. П. Орлова-Давыдова построен дом №10. Дата на фасаде "1886" - год его ремонта. В 1868-1873 годах в доме №41 снимал квартиру Михаил Евграфович Салтыков-Щедрин. С 1872 года более десяти лет в доме №33 жила семья композитора Николая Александровича Римского-Корсакова. Здесь им были написаны оперы "Псковитянка", "Майская ночь", "Снегурочка".
В 1872-1873 годах перестраивался дом №3. В 1873-1874 годах построен дом №27. В 1875-1876 годах построен дом №20. В 1880-х годах существующий облик приобрёл дом №1. В доме №37 жил будущий адмирал и московский генерал-губернатор Фёдор Васильевич Дубасов. В 1883 году в квартире №5 дома №23 жил граф А. А. Голенищев-Кутузов. В 1884-1885 годах построен дом №40. В 1886 году для Сергиевского благотворительного братства по проекту П. С. Самсонова был построен дом №19. В 1887-1895 годах в доме №50 жил писатель Николай Сергеевич Лесков. Здесь В. А. Серовым был написан его портрет.
В 1887 году Кирочный переулок между Фурштатской и Сергиевской улицей был назван Друскеникским. Это название он получил по литовскому городу Друскеники. Нумерация домов здесь идёт в противоположном направлении нумерации всех остальных улиц этого района. По всей видимости это было сделано по ошибке служащего жилищного хозяйства.
В 1892 году для Управления главного военного священника был построен дом №29/18. В 1893 году В. Ф. фон Геккерном был построен дом №25 для К. А. Шрейбера - владельца дома №15. На фасаде этого здания находится владельческий знак Шрейбера - буква "S". В 1895-1896 годах по проекту Петра Ивановича Балинского построен дом №17. В 1895-1897 годах построен дом №58. В 1896-1899 годах построен дом №52. В 1897-1898 годах возведён дом №15. В 1898-1899 годах построен дом №36. В 1900 году на месте участок домов №47 и 49/11 по проекту А. С. Хренова построен дом №47/11. В 1901 году построен дом №2/12, по проекту Карла Валериановича Бальди - дом №28. В 1903-1906 годах построен дом №62 - особняк С. С. Боткина. В 1904-1905 годах по проекту архитектора Шене для Н. В. Спиридонова (хозяина дома №58). был построен доходный дом №60. В 1904-1906 годах в доме №8 жил архитектор Владимир Антонович Косяков.
В 1908-1910 годах построен дом №24. В 1909-1918 годах в доме №34 располагалось посольство США. В 1910-1915 годах в доме №23 жил лейб-медик Евгений Сергеевич Боткин, сын знаменитого профессора С. П. Боткина. Евгений Сергеевич в 1918 году был расстрелян в Екатеринбурге вместе с царской семьёй.
19 мая 1923 года улицу назвали именем Петра Лаврова, в честь революционного деятеля, здесь в своё время проживавшего. В начале 1930-х годов посередине трассы был устроен бульвар, посажены деревья. В 1930-х годах был построен дом №26. После Великой Отечественной войны улицу заасфальтировали. В доме №21 работали Ленинградский городской совет и Ленинградский областной совет ОСОВАВИАХИМа (Общество содействия обороне и авиационно-химическому строительству). В 1937 году построен дом №29/А. В 1938 году по проекту Н. А. Троцкого для хлебозавода был построен дом №38/16 (в настоящее время АО "Арнаут").
В декабре 1952 года Козмодемьянский переулок был назван Мелитопольским (в память освобождения от фашистов в 1943 году города Мелитополя). С 1970-х годов в доме №39 размещается консульство Германии. В доме №44 жил известный по фильмам "Операция Ы", "Полосатый рейс", "В бой идут одни старики", "Я шагаю по Москве" актёр Алексей Макарович Смирнов.
4 октября 1991 года улице было возвращено прежнее название. В 1990-х годах в доме №43 разместилось почётное консульство Австрии.
