В феврале 1936 года Наталья Евгеньевна познакомилась с Сергеем Борисовичем Рудаковым, от него она впервые и услышала о том, что в Воронеже находится Осип Мандельштам. Рудаков не торопился познакомить ее с ссыльным поэтом и его женой – их первая встреча состоялась только в сентябре, причем О.М. напустился на нее за то, что она прочитала наизусть стихотворение «Я потеряла нежную камею…» – самое его слабое, как он тогда полагал. Но очень скоро знакомство перешло в дружбу, и встречи стали почти ежедневными. О.М. и Наталья Штемпель часто гуляли вместе, посещали воронежские музеи и ходили на концерты.

Предупредив дочь об опасности встреч с опальным и ссыльным поэтом, мать Наташи не только не запретила ей встречаться с ним, но и, единственная в это время в Воронеже, принимала его и Н.Я. у себя. Штемпель познакомила О.М. с П.Л. Загоровским, также после этого встречавшимся с поэтом и помогавшим ему материально (последние полтора года Мандельштамы жили в Воронеже без заработков и практически в полной изоляции). О.М. говорил о Наталье Евгеньевне: «Наташа владеет искусством дружбы».

Постепенно у О.М. выработалась привычка читать ей каждое новое стихотворение, а несколько его раннеапрельских стихотворений 1937 года посвящены или обращены непосредственно к ней – «Клейкой клятвой липнут почки…»^>136, «На меня нацелились груша да черемуха…» и «К пустой земле невольно припадая…». А о стихах «К пустой земле невольно припадая..» О.М. сказал ей: «Когда умру, отправьте их как завещание в Пушкинский Дом». Весной 1937 года, незадолго до отъезда из Воронежа, О.М. попросил Н.Я. переписать для Наташи в блокноты все воронежские, а также другие ненапечатанные стихи 1930-х годов. Под каждым воронежским стихотворением О.М. собственноручно поставил дату и букву «В» (Воронеж).

После отъезда Мандельштамов из Воронежа Наталья Евгеньевна несколько раз ездила повидаться с О.М. и Н.Я. в Савелово, Москву и Калинин. Получив от Н.Я. известие о гибели О.М., она поехала к ней в Калинин, а оттуда, по ее просьбе, и дальше в Ленинград – к Ахматовой, чтобы рассказать ей о смерти поэта, сообщать о которой в письме Н.Я. тогда побоялась.

После смерти О.М. отношения Натальи Евгеньевны с Н.Я. не прервались. Они постоянно переписывалась или перезванивались, несколько раз Н.Я. навещала Н.Е. Штемпель в Воронеже, но чаще всего они – обе учительницы – встречались в каникулярное время в Москве или на подмосковных дачах (в Тарусе, Верее, Кратове, Переделкине), куда к Н.Я. приезжала уже Наталья Евгеньевна.

Кроме подаренных О.М. блокнотов (получивших название «Наташина книга»), у Натальи Евгеньевны отложился довольно большой архив поэта: автографы стихов и эпиграмм, стихи, записанные Н.Я. на узких полосках ватмана, которые ей отдавал О.М. по мере написания, а также «Ода Сталину» (О.М. просил уничтожить ее, но она ее все-таки сохранила). После смерти Мандельштама Н.Я. передала Наташе на хранение подлинники всех писем О.М. к ней, а также второй список всех ненапечатанных стихов, включая воронежские. Всё это она сберегла, унеся из Воронежа накануне занятия города немцами, – погибли только письма к самой Н.Е. Штемпель – от О.М., от Н.Я., от С.Б. Рудакова.

После войны Наталья Евгеньевна продолжала хранить этот архив (за исключением 1948–1951 годов, когда он находился в Киеве у Маруси Ярцевой – близкой подруги Натальи Евгеньевны, которую она в свое время познакомила и с О.М., и с Н.Я.). Не позднее середины 1950-х годов Наталья Евгеньевна возвратила Н.Я. не только всё доверенное ей на хранение, но и то, что О.М. подарил лично ей (оставив себе только книги, надписанные О.М.