Здание построено в первой четверти XIX века для Комиссии духовных училищ, которой тогда принадлежал этот участок. Для Духовно-учебного управления при Синоде в 1851-1856 гг. арх. А. С. Кудинов произвел ряд переделок. В 1873-1874 гг. по заказу новой владелицы Ю. А. Воейковой арх. К. И. Реймерс изменил вид фасада в стиле зрелой эклектики, оформив его рустовкой, пилястрами и богатой лепниной с изящной деталировкой.

Здесь работали отделение крупной московской фирмы «В.Высоцкий и Ко.», Центральный банк обществ взаимного кредита, товарищество чайной торговли.

В 1920-е годы в доме жил драматург Евгений Шварц – это был его первый петербургский адрес. Весной 1924 года в в кв.1 у К.И.Бернгардта, бывшего владельца «депо роялей»), останавливался Максимилиан Волошин.

В начале 1990-х гг. во время работ по реконструкции дома 57 по Невскому пр. под отель «Невский палас» все соседние здания (Невский пр., 55 и 59, Стремянная ул., 10) дали угрожающие неравномерные просадки вследствие строительства подземного комплекса гостиницы без предварительного гидрогеологического обследования всего участка и проведения защитных мероприятий по укреплению грунтов и соседних фундаментов. Все эти здания пришлось немедленно расселить.
После этого аварийные дома довольно долго стояли заброшенными.

В 2001 году погрязший к тому времени в многомиллионных долгах «Невский палас» был куплен гостиничной сетью «Corinthia Hotels International», которой были переданы и оба прилегающих участка по Невскому с полуразрушенными зданиями для организации там дополнительных корпусов гостиницы.

20 февраля 2001 г. приказом КГИОП № 15 дома 55 и 59 были включены в список вновь выявленных объектов культурного наследия. Тем не менее, несмотря на охранный статус, в 2005-2006 гг. оба здания были снесены до основания.

Строительные работы на месте разрушенного дома 59 затянулись на четыре года и закончились только к 2010 году. Вид синего забора на Невском не раз вызывал гнев губернатора Петербурга.

Соседи дома 59 неоднократно заявляли (в том числе и в судебных инстанциях), что стройка наносит вред окружающим зданиям. Например, представители банка «Глобэкс» утверждали, что независимой экспертизой доказано — затопление, зафиксированное представителями КГИОП по адресу Невский пр, 61 (где находится филиал банка) вызвано именно работами на Невском 59. Эти работы привели к деформации основания, раскрытию трещин в стенах и нарушению гидроизоляции подвальной части дома 61.

В новом здании, выстроенном в железобетоне, в соответствии с проектом располагается второе крыло отеля «Невский палас», так называемое «executive wing» (107 номеров представительского класса, президентский люкс и конференц-зал на 540 человек).
Проект реконструкции фасадов разрабатывала архитектурная мастерская «Литейная часть-91» под руководством Рафаэля Даянова. Генеральным проектировщиком проекта выступила британская архитектурная и инженерная компания ARUP.

При заявленном «воссоздании» здание было надстроено дополнительными этажами с обильным остеклением. Внутренние интерьеры полностью заменены и выполнены в стилях арт-деко и модерна.

Летом 2009 года, когда на месте исторических домов 55 и 59 уже стояли «новоделы», охранный статус с обоих участков был снят (Распоряжение КГИОП N 10-16 от 09.06.2009).