Этот участок на углу Невского проспекта и Троицкой (ныне Рубинштейна) улицы впервые был застроен в начале XIX века трёхэтажным каменным домом. Он принадлежал купцу Н. С. Паскову-Шарапову (владел и соседним домом №47), затем полковнику И. Ростовцеву.
В 1858 году в доме №45 по Невскому проспекту разместилось Мариинское женское училище "для приходящих девиц", в 1862 году переименованное в Мариинскую женскую гимназию (первую в Петербурге). Организатором и начальником учебного заведения был Н. А. Вышнеградский.
В 1875-1877 годах дом был перестроен для сына прежнего владельца - генерала-майора И. И. Ростовцева. Работу выполнил архитектор А. Л. Гун. Здание им было надстроено до пяти этажей, фасад переоформлен в эклектичном стиле. Дворовые корпуса построены по проекту П. Ю. Сюзора. Перила мраморных лестниц выполнены в мастерской Л. И. Фосса.
В конце XIX - начале XX века здесь работали фотоателье Тауба, конторы правления Русского общества пароходства и торговли, Пароходного общества на Волге, банкирского дома "Захарий Жданов", Столичного общества взаимного кредита.
В начале XX века дом принадлежал Д. И. Филиппову, владельцу сети петербургских и московских булочных. Здесь он открыл кондитерскую-кофейню, отделкой интерьера которой занимался архитектор Л. А. Ильин. В 1911 году угловой вход был оформлен гранитным порталом.
Летом 1906 года в одной из квартир дома №45 проходила конспиративная встреча В. И. Ленина и П. Н. Лепешинского.
В 1950-х годах в помещении бывшей булочной открылось первое в Ленинграде кафе-автомат. Автоматическое обслуживание вскоре сломалось и заведение превратилось в обыкновенную столовую. Горожанами она была прозвана "гастритник".
В 1997 году у дома №45 был убит вице-губернатор Петербурга, председатель КУГИ М. В. Маневич. В 2000-х годах помещение столовой занял кафе-ресторан McDonalds.
