Участок дома №25 по Миллионной улице с 1717 года принадлежал генерал-адмиралу графу Николаю Фёдоровичу Головину. На месте особняка Головина несколько позже появилось новое трёхэтажное здание, которое возможно спроектировал архитектор П. Е. Еропкин.
С конца XVIII века участок принадлежал графу Ивану Павловичу Кутайсову. После убийства Павла I Кутайсов был уволен со службы, он выехал за границу. В дальнейшем здесь жили его наследники. В это время соседний участок дома №24 по Дворцовой набережной принадлежал "жене обер-гардеробмейстера А. П. Кутайсовой". Старший сын графа Павел был председателем Общества поощрения художеств. Возможно по этому с начала XIX века здесь жили художники. В 1809 году одним из жильцов дома на Миллионной улице был живописец Тимофей Алексеевич Васильев. Позже здесь находилась мастерская художника Г. Г. Чернецова. С Кутайсовыми был близко знаком А. С. Пушкин. В 1832 году он позировал Чернецову для картины "Парад на Марсовом поле". После смерти графа Кутайсова участком владела его вдова.
В 1843 году здесь поселилась польская графиня Эвелина Ганская. Она проживала "в голубом салоне с окнами на Неву", то есть в доме со стороны Дворцовой набережной. Но навещавший её писатель Бальзак указывал, что встречался с ней в доме на Большой Миллионной. По всей видимости, оба владения в это время воспринимались как единое целое.
К концу 1840-х годов дом №25 принадлежал графине Марии Ивановне Васильевой, жене бывшего генерал-майора и действительного статского советника В. Ф. Васильева. В 1859-1860 годах архитектор Г. М. Барч перестроил особняк для В. И. Трофимова. В 1913 году дом был перестроен по проекту И. А. Претро. В это время участком владел отставной генерал-лейтенант Сергей Николаевич Плаутин. Кроме здания на Миллионной улице ему принадлежало ещё два дома в Петербурге. Здесь же жил сын С. Н. Плаутина Михаил, служивший в канцелярии Совета министров.
