И девичий сон сбылся. «Вся сфера небесная для меня переменилась», — вспоминала она об этих днях через много лет. К пятнадцатилетней Наташе посватался Иван Долгорукий, вероятно, наслышанный о ее красоте и богатстве. Она не знакома была с ним до сватовства, но вряд ли не знала о его похождениях в Москве. Но ни словом не обмолвится она об этом горьком знании о женихе, да и видно по словам ее, что влюблена она в него была с первого взгляда. Иван был хорош собой, весел, к тому ж умел нравиться. Чего же еще было желать юной Наташе. «Думала, я — первая щастливица в свете, потому что первая персона в нашем государстве был мой жених, при всех природных достоинствах имел знатные чины при дворе и в гвардии. Я признаюсь вам в том, что я почитала за великое благополучие, видя его к себе благосклонна; напротив тово, и я ему ответствовала, любила ево очень, хотя я никакова знакомства прежде не имела... но истинная и чистосердечная ево любовь ко мне на то склонила».
Многие историки подвергали сомнению искренность чувств Долгорукого к Наталье Борисовне, мол, знал он и о ее богатстве, был и охоч до женского пола. Но уж очень искренни слова и наблюдения Натальи Борисовны, и, кроме того, бывает так в Жизни, что даже ловеласы многогрешные, встретив искреннюю чистоту и любовь, нрав свой укрощают и проникаются душевным теплом к столь незапятнанной любви. К тому же, несмотря на дурные склонности князя Ивана, многие отмечали в нем простоту, душевность и отсутствие коварства. Тот самый дюк де Лирия, строгий в характеристиках к русским придворным, так отзывался о князе Иване, водившем с ним дружбу: «Государь любил его так нежно, что делал для него все, и он любил государя так же. Ума в нем было мало, а проницательности никакой, но зато много спеси и высокомерия, мало твердости духа и никакого расположения к трудолюбию, любил женщин и вино, но в нем не было коварства. Он хотел управлять государством, но не знал с чего начать, мог воспламеняться жестокой ненавистью, не имел воспитания и образования, словом, был очень прост». Конечно, де Лирия, как всякий иностранец, не способен был понять особенности русской души, конечно, в этой характеристике есть и доля правды, но и сам посланник отмечает отсутствие коварства и широту души, которую он называет простотою. Удивительно кстати сказать, что иностранцы всегда упрекают нас в простоте и отсутствии трудолюбия, и если второе нередко справедливо, то первое — тот самый из наших недостатков, которые часто переходят в достоинства.
Так и юная Наталья рассмотрела в Иване более, чем смог рассмотреть иностранец, как всякая русская женщина, почувствовала сердцем, а не умом суженного. «Казалось, ни в чем нет недостатку. Милой человек в глазах, в разсуждении том, что этот союз любви будет до смерти неразрывной, а притом природные черты, богатство; от всех людей почтение, всякой ищет милости, рекомендуютца под мою протекцию». Природные черты — это, конечно, хорош собой, да к тому же еще богат, а еще велеречив и сумел рассказать о любви до самой смерти, рассказать искренне, без коварства. Но еще очень важно, что и к Наташе отношение всех окружающих изменилось, раньше никто и не замечал, теперь же все добивались протекции, заглядывали в глаза. «Все кричали: «Ох, как она щаслива!» Моим ушам не противно было это эхо слышить». Дочке фельдмаршала, юной графине, конечно, весьма лестно было прельстить такого жениха.
Предложение князя Ивана было с радостью встречено и родственниками графини, которые стремились породнить Шереметевых с могущественным и приближенным к царю кланом Долгоруких. Они скоро обсудили все брачные статьи будущего брака, и накануне Рождества состоялся торжественный обряд обручения, по-русски сговор, Ивана и Натальи в присутствии царя, всей императорской фамилии, невесты императора Екатерины, иностранных министров, придворных и многочисленных родственников с обеих сторон. Обручение проводили один архиерей и два архимандрита, все комнаты были заполнены гостями. Обручальные кольца стоили по тем временам неимоверных денег, перстень Натальи — шесть тысяч, а перстень Ивана — двенадцать тысяч рублей. Кроме того, одарили их несметными подарками, богатыми дарами, бриллиантовыми серьгами и украшениями, «часами, табакерками и готовальнями и всякою галантерею», а еще подарили «шесть пуд серебра, старинные великие кубки и фляши золоченые», столько всего, что Наталья едва могла это принимать, и ей помогали ее родственники. Все, что можно было придумать для увеселения гостей, было сделано. На улице собрался народ, закрыв выход для всех карет, и радостно приветствовал дочь фельдмаршала.
Но счастие не может длиться долго — для Натальи сроку ему было 24 дня.
6 января 1730 года на берегу Москвы-реки собрались толпы народу — смотрели, как рубят прорубь в день водосвятия, как бросались в прорубь смельчаки, пар поднимался над водой от их дыхания. Радостно возбужденный наблюдал эту картину с запяток саней своей невесты император. День был ясный, морозный, но не уберегся юноша, простыл, переохладился, слег к вечеру, а через несколько дней все увидали следы явных признаков оспы на его теле. В день, когда должны были состояться две свадьбы, императора с Екатериной Долгорукой и Ивана с Натальей, случилось несчастье — Петр II умер.
Семейство Долгоруких, не найдя ничего лучшего и понимая всю бедственность своего положения, на семейном совете решилось на страшное по тем временам государственное преступление — составление подложного завещания императора, в котором тот передавал престол своей невесте Екатерине Долгорукой. Затея была Алексея Григорьевича, но довести до конца ее должен был Иван, неотлучно находившийся у постели больного. Он должен был дать Петру завещание на подпись, как только император придет в сознание, и заставить его подписать. Одновременно был изготовлен второй экземпляр духовной, в которой Иван подделал подпись Петра II, что, как оказалось, он не раз уже делал по разрешению царя. Но Петр умер, не приходя в сознание, а авантюра была настолько шита белыми нитками, что рассыпалась, как только на заседании Верховного тайного совета Долгорукие предъявили это подложное завещание. Их просто не стали слушать, осыпали насмешками и по предложению князя Д. Голицына решили пригласить на российский царский престол курляндскую герцогиню Анну Иоанновну — дочь царя Иоанна Алексеевича, старшего брата Петра Великого. «Сделалась коронная перемена», — пишет Наталья Борисовна. Прямая мужская ветвь наследования Романовых оборвалась, и верховники надеялись ограничить власть Анны специальными «кондициями», чтобы закрепить свою власть. Но «затейка верховников» не удалась. Приехавшая в начале февраля Анна, воспользовавшись поддержкой многочисленного неродовитого дворянства, собравшегося в столицу на свадьбу императора, разорвала «кондиции». Тем самым она решила участь верховников, да и к тому же — и Долгоруких.
В тревоге и слезах наблюдала Наташа развитие событий. «Я довольно знала обыкновение своего государства, что все фавориты после своих государей пропадают, чево было и мне ожидать», — пишет она. Все родственники съехались к ней в дом, жалея об ее участи и уговаривая ее не губить свою молодость и отказать своему жениху. Уже был подготовлен и новый жених, который, как утверждали, «не хуже ево достоинством», разве только не в тех чинах. Наверное, это было бы самое разумное решение, коль скоро всем известна была тяжелая участь тех, кто впадал в немилость царскую. Но сердце доброй девушки уже было отдано навсегда: «Войдите в рассуждение, какое это мне утешение и честная ли эта совесть, когда он был велик, так я с радостию за нево шла, а когда он стал нещаслив, отказать ему. Я такому безсовестному совету согласитца не могла, а так положила свое намерение, когда сердце одному отдав, жить или умереть вместе, а другому уже нет участие в моей любви. Я не имела такой привычки, чтобы севодни любить одново, а завтре — другова... я доказала свету, что я в любви верна: во всех злополучиях я была своему мужу товарищ. Я теперь скажу самую правду, что, будучи во всех бедах, никогда не раскаивалась, для чево я за нево пошла, не дала в том безумия Бога; Он тому свидетель, все, любя ево, сносила, сколько можно мне было, еще и ево подкрепляла».