Существует предположение, что общее планировочное решение (местоположение и форма здания в плане) принадлежало самому Александру!. Якобы он, проезжая вместе с князем А. Я. Лобановым-Ростовским по Исаакиевской площади, выразил неудовольствие ее видом. Так это было или нет, неясно. Но участок треугольной формы общей площадью 5400 кв. м у начавшегося строиться по проекту того же О. Монферрана Исаакиевского собора действительно в 1817 г. пожалован князю императором. Официально он был оформлен на его супругу, К. И. Лобанову-Ростовскую (в девичестве Безбородко).
В 1818 г. в «Книге для записей планов и фасадов, выдаваемых обывателям 1-й Адмиралтейской части», которая велась в Комитете для строений и гидравлических работ, была сделана запись о том, что князь А. Я. Лобанов-Ростовский «желает по приложенным фасадам построить каменный дом», а рядом имеется приписка, что хозяин «обязался кончить оный, вывесть и покрыть непременно к ноябрю будущего 1819 года».
Для строительства дома создали специальную контору. Работы начали зимой 1818 г. с забивания в неустойчивый болотистый грунт свай. На сваях устроили ленточный фундамент из бутовой плиты, заглубленный почти на 3 м. Уже весной приступили к кладке стен. Балки перекрытий делали из бревен (красной сосны) диаметром 30 см. Сами перекрытия делали из дуба. Крышу крыли листами черного железа с заводов Яковлева, а лестничные перила и ограду балконов отливали из чугуна. Капители и базы колонн в вестибюле отлили из бронзы на заводе Берда. Внутренние отделочные работы завершились в 1820 г.
По инициативе супруги князя значительная часть здания изначально задумывалась как доходный дом. Уже в 1819 г., т. е. еще до окончания строительства, Лобановы-Ростовские начали сдавать в новом доме помещения.
Уже летом 1821 г. здесь на первом этаже снял помещение художественный магазин братьев Леончини. Согласно рекламе, в нем продавалось, например, «весьма хорошее собрание всякого рода алебастровых ваз различной величины, ламп и других вещей».
В 1824 г. сумма ежегодного дохода от сдаваемых помещений достигла 100 тыс. руб. Вот что и кому сдавалось:
— полуподвальная угловая квартира со стороны Вознесенского проспекта под первую в городе литографию;
— квартира литографа Петерса (на первом этаже);
— помещения под мелочную и мучную лавки (на первом этаже);
— помещения для Комиссии строительства Исаакиевского собора (на первом этаже);
— полуподвальная угловая квартира со стороны Исаакиевской площади под портерную;
— квартиры для сапожника и перчаточника (на первом этаже);
— помещения для Провиантского департамента Военного министерства (на первом этаже);
— квартира с видом на Исаакиевскую площадь и Вознесенский проспект (в бельэтаже);
— помещения (в бельэтаже) под Космораму (стереоизображения европейских городов и сражения армий Александра Македонского и персидского царя Дария при реке Граник), устроенную гамбургским художником Суром (стоимость билета составляла 2,5 рубля с человека);
— помещения для Провиантского департамента Военного министерства (большая часть помещений бельэтажа);
— квартиры закройщика Шпицбарта, мастера альфрейной живописи Мартушевича и некоего господина Орлова (на третьем этаже);
— помещения под пансион госпожи Орсениус (на третьем этаже).
На третьем этаже находились также комнаты управляющего.
В доме Лобановых-Ростовских регулярно проводились различные светские и культурные мероприятия. В журнале «Отечественные записки», например, можно было прочитать: «Для любителей французского языка Господин Сен-Мор и нынешним Великим постом продолжил свои литературные вечера. Он читает лучшие места из Корнеля, Расина, Мольера и других драматических писателей, а также из Буало, Вольтера, Делиля и проч. Подписка на 10 таковых вечеров стоит 75 руб. с персоны. Чтение происходит в новом доме княгини Лобановой-Ростовской».
В парадной анфиладе со стороны Адмиралтейства известный художник и театральный декоратор А. Тозелли (автор «Панорамы Петербурга» с башни Кунсткамеры, выполненной в 1827 г.) устроил выставку «Сценография Иерусалима и святых мест, окрест его лежащих». По свидетельствам посетителей, рисунок иерусалимского источника Силье дополнялся звуком журчания воды. Вход на его выставку стоил 5 руб.
Свое название «дом со львами» здание получило после выхода в свет поэмы А. С. Пушкина «Медный всадник», в которой герой спасается от наводнения, сидя верхом на каменном льве. Пара этих львов, высеченных из каррарского мрамора, стоит с двух сторон от главного входа в здание со стороны Адмиралтейского проспекта. Они были изготовлены в 1810 г. в Италии, в мастерской П. Трискорни по античным образцам.
Описывая злоключения героя поэмы во время наводнения, А. С. Пушкин написал следующие строки: