Участок дома №51 по Большой Морской улице в 1740-х годах был занят строением гвардии сержанта Петра Петровича Нарышкина, приходившегося дальним родственником владельцам домом №31 и 48 по этой же улице. Этот дом выглядел богаче соседних, так как над своей средней частью имел мезонин в три окна с аттиком и маленький треугольный фронтон над средним окном перед аттиком.
В 1764 году секунд-майором Петром Петровичем Нарышкиным участок был продан Матрёне Павловне Салтыковой. Новая владелица являлась женой действительного камергера Сергея Васильевича Салтыкова, который по легенде мог быть отцом Павла I. В 1770-х годах особняк принадлежал Михаилу Сергеевичу Потёмкину, чья жена после его смерти владела домом №47.
С конца XVIII века дом №51 по Большой Морской принадлежал английскому купцу Якобу Мейбому. В 1838 году им распоряжались его дочери Елизавета и Юлия, которые продали участок коллежскому асессору Петру Дмитриевичу Салтыкову. Тот приходился внуком фельдмаршалу Н. И. Салтыкову, с одним из предыдущих владельцев он состоял в дальнем родстве.
После 1841 года особняк был в руках подполковницы Елизаветы Ивановны Брюн. Она начала перестройку здания, но вскоре скончалась. Дом стал долгостроем. В 1845 году здесь находилось двухэтажное на высоких подвалах строение. Газета "Северная пчела" писала о том, что оно портит вид Большой Морской улицы.
Незавершённую постройку у малолетних наследников выкупила вдова Ивана Дмитриевича Салтыкова (брата Петра Дмитриевича) Елизавета Павловна. Она приходилась внучкой графу А. С. Строганову. В Русском музее хранится её портрет, написанный К. П. Брюлловым. Для Елизаветы Павловны здесь был построен новый двухэтажный особняк. Сначала предполагалось сделать его доходных домом, но затем было решено использовать его в качестве личного жилища владелицы. Строительство начинал архитектор Г. П. Пономарёв, продолжал П. С. Садовников, завершил Г. Э. Боссе. Салтыковы были постоянными заказчиками последних двух. До сих пор сохранились некоторые созданные тогда элементы отделки интерьеров: плафоны потолков, настенная лепнина, мраморные камины.
В 1854 году в доме №51 жил тайный советник, член Государственного совета князь Павел Павлович Гагарин. В 1855 году Салтыкова продала участок молодому графу Павлу Андреевичу Шувалову, женившемуся на совладелице дома фрейлине Ольге Эсперовне Белосельской-Белозерской. Здание стало использоваться как доходный дом. В 1860-х годах одну из квартир занимала баронесса Юлия Петровна Вревская.
Шуваловыми в 1868 году здание было продано тайному советнику Владимиру Павловичу Александровскому. Спустя 10 лет по духовному завещанию оно перешло его вдове. При ней дом в 1898 году дом был надстроен третьим этажом, оборудован новой лестницей с лифтом. После смерти Е. И. Александровской зданием владели ей сыновья С. В. и В. В. Александровские, дочери О. В. Енгалычева и Е. В. Шаховская. Сергей Владимирович Александровский во время русско-японской войны был распорядителем Российского общества Красного Креста при главнокомандующем. Позже он служил губернатором в Пензе, где был убит террористом.
В 1904-1905 годах совладельцем дома №51 стал купец В. А. Петров. В 1905 году Енгалычева, Шаховская и Петров участок продали. Последней частной владелицей здания стала миллионерша Мария Васильевна Варпаховская, вдова полковника. В газетах отмечалось, что она устроила в своём доме приют для бездомных собак. Мария Васильевна умерла от рака в 1913 году. Прибывшие в её дом полицейские насчитали здесь 40 собак и кошек, каждая из которой имела отдельную идеально чистую комнату. Прислуга ежедневно покупала для них 18 фунтов филейной вырезки и 9 кур. Наследники владели домом №51 ещё два года, а затем продали его одному из страховых обществ.
В 1920-х годах помещения занимал Ленинградский трест кожевенной промышленности, перед войной - тресты "Дубитель" и "Главкожзаменитель". До недавнего времени здесь работал Военный комиссариат Центрального района.
