Однако жену Алексей Константинович себе выбрал под стать матери. Его избранницей стала дворянка из старинного, но обедневшего рода Бахметевых, жена ротмистра Миллера – Софья. Красотой она, правда, не отличалась и по чертам лица более походила на мужчину: тяжёлый волевой подбородок, высокий лоб… Но это была женщина большого ума, прекрасно разбиравшаяся и в литературе, и в музыке. Они встретились в январе 1851 года, ему было тридцать три года, ей – чуть меньше. Уезжая с маскарада, Алексей Константинович повторял про себя пришедшие вдруг в голову слова: «Средь шумного бала, случайно…» Так, по легенде, родилось стихотворение «Люблю ли тебя – я не знаю, но кажется мне, что люблю!..». На том же балу с Софьей Миллер познакомился и другой наш классик – Иван Сергеевич Тургенев, но не нашёл в ней ничего примечательного и вскользь заметил: «Лицо чухонского солдата в юбке».
После долгожданного развода Софьи с её ротмистром А.К. Толстой обвенчался со своей подругой в Дрездене в 1863 году. Софья Андреевна Миллер стала графиней Софьей Андреевной Толстой – именно она занимала позицию первой дамы золотого века русской литературы, пока её не сменила полная тёзка, «графиня Софья Андреевна— младшая», супруга Л.Н. Толстого, гостеприимная хозяйка Ясной Поляны и знаменитого пруда, в котором не раз пыталась демонстративно топиться.
«Старшая» Софья Андреевна не сохранила почти ничего из черновиков или дневников А.К. Толстого. Вместе с дочерью маникюрными ножницами они вырезали из писем то, что казалось им неподходящим для публикации. По воспоминаниям очевидцев, вдова А.К. Толстого письма сжигала пачками, отбирая для публикации совсем немногое, предварительно сократив и это немногое до минимума. Первое место по количеству сохранившихся писем среди адресатов занимает сама Софья Андреевна Миллер-Толстая. Она ничего не оставила из переписки Толстого с матерью и дядей А.А. Перовским, который называл Алексея Константиновича сыном, а тот его отцом – эти письма, по-видимому, смогли бы пролить свет на тайну происхождения писателя. Почти всё, что не успел опубликовать сам А.К. Толстой, утрачено или уничтожено руками его вдовы. Сохранились лишь две записные книжки, одна тетрадь и несколько отдельных листов. Верный семейным обычаям предков, Алексей Константинович не раз давал супруге повод для ревности, и исследователи склонны считать, что расправа с его наследием – месть обиженной женщины. Однако сама Софья Андреевна оправдывала свои действия завещанием А.К. Толстого, который просил не печатать того, что имеет «исключительно личный характер».