Дом был построен в 1910—1912 годах по заказу генерал-майора Михаила Павловича Толстого. Архитектором выступил русско-шведский специалист, академик Императорской Академии художеств, барон Федор Иванович Лидваль, благодаря которому в Петербурге появилось несколько уникальных домов в стиле «Северный модерн». Характерными чертами архитектуры, которые воплотил Лидваль стали высоченные «ренессансные» проезды-арки и лоджии на верхних этажах. В сложную планировку здания включена последовательность трёх соединённых арками проходных дворов, ведущая с улицы Рубинштейна на набережную реки Фонтанки. Таким образом по замыслу Лидваля была устроена некая внутренняя улица, иногда поэтически называемая улицей зодчего Лидваля.
В отделке фасадов под контролем техника Дмитрия Давыдовича Смирнова использовались тёсаный известняк, кирпич и штукатурка.
Этот дом как и дом на Каменноостровском пр.26-28 был образцом комфортного проживания: при строительстве было сразу предусмотрено лифты, прачечная, водопровод. Однако это не значило, что дом задумывался как «элитный», в нем были квартиры и для скромного проживания и роскошные апартаменты.
После смерти генерал-майора владелицей дома с 1913 года стала его вдова графиня Ольга Александровна Толстая.
В 1918 году дом был национализирован и облик дворов был значительно изменён: посередине дворов, в проездах, были разбиты газоны, на которых были высажены тополя, а вместо восьмиугольной клумбы был установлен фонтан с бетонным вазоном посередине.
Сейчас дом находится в охранном статусе «зона регулируемой застройки».
