Участок дома №28 по Большой Морской улице (№13 по Гороховой) в 1738 году был отдан тайному советнику сенатору Василию Яковлевичу Новосильцеву. В то время он был сквозной, простирался вплоть до Мойки. Новосильцеву указывалось построить со стороны реки дом в два этажа, тогда как со стороны Гороховой улицы в один, а Большой Морской - в один на высоких погребах. К 1740-х годах со стороны последней стояло именно такое строение в 11 осей с центральным ризалитом в три окна. Справа располагались въездные ворота.
В 1740-х годах участок был поделен надвое, Новосильцеву досталась территория со стороны Большой Морской улицы. В 1743 году Василий Яковлевич скончался, участок перешёл его сыну Александру [2, с. 53]. Тогда же здесь поселился купец Христофор Мейер, который сам в свою очередь селил у себя жильцов. В 1762 году Александр Васильевич Новосильцев, успевший дослужиться до секунд-майора и выйти в отставку, продал дом жене поручика Марье Петровне Травиной за 12 000 рублей. Спустя 15 лет она заложила дом, а вскоре продала.
В 1797 году участком владел генерал-майор Андрей Гаврилович Чернышёв. Он был здесь хозяином, по всей видимости, до 1806 года. Дом унаследовал его племянник Павел Петрович, владевший им ещё в 1809 году. От него участок достался штаб-лекарю Клавдию Серкле, а в 1812 году - коллежской советнице Алевтине Ивановне Толстой (Толстовой). Тогда же по заказу Алевтины Петровны здесь было построено двухэтажное каменное здание, стоимость двора была оценена в 100 000 рублей.
Спустя три года Толстая продала дом статскому советнику Афанасию Никитичу Тулубьеву. В 1816 году он просил разрешения подключить его к уже существующей на Большой Морской улице канализации. Тулубьев надстроил корпус со стороны Большой Морской до четырёх этажей. Со стороны Гороховой улицы дом был двухэтажным. В 1837 году здесь жил Иван Александрович Лобанов-Ростовский.
Дом Тулубьева в 1850-х годах был заполнен торговыми заведениями. Здесь работал модный магазин Луары Буланже, модно-галантерейный магазин В. Кене. С ними соседствовал бриллиантщик Иоганн Бек.
Афанасий Никитич Тулубьев скончался в 1857 году. От него дом №23/13 перешёл к полковнику Ивану Фёдоровичу Тутолмину, дослужившегося до генеральского звания. При нём здесь работало "Депо фабрики турецкого табаку и папирос торгового дома для караимов С. Габая и А. Мерчи". В 1869 и 1880 годах дом Тутолмина перестраивался архитектором П. Ю. Сюзором. При первой из перестроек здание стало пятиэтажным. Первый этаж вместил сапожный магазин, свечную лавку и колбасную. В остальных этажах располагались квартиры.
В 1903-1917 годах здание принадлежало Ивану и Николаю Николаевичам Тутолминым. До 1911 года здесь работал магазин ювелирной фирмы Тилландер, позже переехавшей в другое место (Невский пр. 26). В 1900-х годах здесь открылись кофейня "Универсаль", Славянский лазарет и Французский институт. В доме №13 размещалось правления основанного в 1913 году акционерного общества "Рубероид".
В 1979 году помещения бывшего дома Тутолминых были отданы администрации Центрального телефонного узла, службам ЛГТС. Работающим в области связи организациям здание принадлежит до сих пор.
