В Москве княжна жила в родительском доме, слишком огромном для нее одной, но где воспоминания об отце казались не столь острыми. Друзья уговаривали ее начать выезжать, чтобы развлечь себя. Однажды в одном из салонов она обратила внимание на мужчину среднего роста, с кудрявыми волосами, печальным взглядом и усами, закрученными книзу. На нем прекрасно сидел мундир, он хорошо говорил по-французски. Его представили: граф Николай Ильич Толстой. Мария держалась с ним мило, ничем не выдавала своих чувств. Но встреча была подготовлена, и уже на следующий день представители обеих сторон начали вести переговоры о возможной женитьбе.

Граф Николай Ильич Толстой без энтузиазма относился к союзу с девушкой внешности столь непривлекательной, к тому же бывшей старше его на пять лет. Но он был на грани разорения, и только выгодный брак мог спасти его. А происхождение давало все основания рассчитывать на благосклонность любой богатой наследницы. Толстые считали себя потомками литовского рыцаря Индроса, который осел в Чернигове в XIV веке и принял там крещение. Праправнук Индроса получил от великого князя Василия Темного прозвище «Толстый». Петр Андреевич Толстой при Петре I был назначен послом в Константинополь, а затем начальником Тайной канцелярии. В 1724 году получил за заслуги титул графа, но дни свои закончил в темнице в Соловецком монастыре, куда был брошен за участие в интригах против Меншикова. Менее знаменитый, чем его предки, Илья Толстой довольствовался тем, что промотал свое состояние, а затем и состояние жены, урожденной Горчаковой: он отправлял стирать белье в Голландию, рыбу к его столу доставляли прямо с Черного моря, он давал бесконечные балы и театральные представления в своем поместье недалеко от Белёва, проигрывал деньги в ломбер и вист. Погрязнув в долгах, согласился на пост губернатора Казани. Тем временем его семнадцатилетний сын Николай отправился в армию: шел 1812 год, в Россию вступил Наполеон, молодежь была охвачена патриотическим пылом. Начав службу гусарским корнетом, Николай скоро становится адъютантом генерала Горчакова, близкого родственника по матери.