В 1964 году Наталия Шаховская вошла в состав трио с Евгением Малининым и Эдуардом Грачом, которое просуществовало более двадцати лет.
О зарождении трио Наталия Николаевна вспоминала :
« Существует море изумительной камерной музыки, там сокровища! Обратите внимание на биографии многих выдающихся исполнителей, как правило, они во второй половине жизни погружаются в этот богатый мир. У меня это произошло раньше. Совершенно случайно. Эдуард Грач и Евгений Малинин выступали с Михаилом Хомицером. У них был запланирован концерт в Одессе, они должны были играть тройной концерт Бетховена, но почему-то рассорились. Сейчас точно не помню, кто именно предложил мне участвовать в этом ансамбле, но я согласилась с радостью, поскольку тройной концерт еще не играла. Выступление намечалось на декабрь, а предложение поступило в сентябре. Тогда у меня был очень напряженный график гастролей, и я сказала: «Хорошо, я вам позвоню, когда буду готова». Через месяц ко мне в консерватории подошел Евгений Васильевич и спрашивает: «Что ж вы нам не звоните?». Я ему резко ответила, что теребить меня не надо, я всё помню и позвоню сама. Малинин тогда сказал Грачу: «Ну, со стервой мы связались!» Мы вскоре встретились, порепетировали и успешно сыграли концерт. У нас сразу сложилась великолепная атмосфера, и творческая, и дружественная. Между нами были замечательные отношения, и это счастливые годы музицирования. У нас на гастролях было такое шутливое распределение ролей : Эдуард Давидович — «администратор», Евгений Васильевич — «художественный руководитель», а вот мне они никак не могли придумать «должность» и говорили : «Это толпа, народ.» »
Все трое артистов были сольными исполнителями. Но, несмотря на большую занятость, участие в трио занимало важное место в творчестве каждого :
« Концерты наши не так часты, поскольку каждый из нас ведет интенсивную сольную деятельность и нам собраться очень трудно. Но одну или две поездки в год мы совершаем обычно вместе. Первое, с чего мы начали нашу встречу, было трио Бетховена. И сейчас мы довольно часто играем бетховенские трио и вообще все его сочинения, в том числе тройной концерт. Это вообще мой любимый композитор, на котором никогда не перестаешь учиться, учиться многим аспектам в музыке. Играем русскую музыку и современную: Чайковского, Рахманинова, Шостаковича, Трио Свиридова. Когда мы играем такую программу как б=дурное большое трио Бетховена и трио Чайковского, то после концерта нельзя сказать, что это легче, чем собственный сольный концерт, по твоим эмоциональным и физическим затратам. »
За годы концертной деятельности трио произошло много курьёзных случаев :
« У меня рушилась виолончель во время выступления. Это было во время моих гастролей в Японии. Тогда я впервые попала в эту страну. Была осень. На улице стояла жуткая жара. Я открыла окно, включила кондиционер в номере и закрыла инструмент в футляре. За день до концерта он пришел в такое состояние, настолько опустился гриф и струны, что я поняла : концерт завтра в Токио я не смогу играть. Я поняла, что современные сочинения, например, сонату Прокофьева еще можно сыграть, но такое сочинение как соната Шуберта мне исполнить не удастся. С помощью моего коллеги профессора (имя неразборчиво) я попала к старейшему японскому мастеру. Я сказала ему: «Я должна сыграть во что бы то ни стало!» И он взял мой инструмент, буквально со слезами на глазах резал мою подставку. Он подпиливал её на миллиметр, выносил ко мне и говорил : «Ну что, достаточно?» — «Ещё, ещё», — непреклонно отвечала я. В общем, я уничтожила подставку. А когда приехала домой, я сразу же поехала в Куйбышев, где у нас был концерт трио с Евгением Малининым и Эдуардом Грачом. Это был симфонический концерт, где мы играли тройной концерт Бетховена и двойной концерт Брамса, а Малинин в этом же концерте играл сначала какой-то фортепианный концерт. И вот когда Малинин уже заканчивал свою игру, а я в артистической взяла свою виолончель, чтобы приготовиться к выходу на сцену, у меня в руке осталась одна голова : сказались последствия совершенного по моему настоянию вынужденного варварского ремонта : виолончель развалилась. За мной пришел Грач, нам уже надо было выходить на сцену, и вдруг он видит, что я стою в комнате, а виолончель вся разобрана по частям. Я в таком виде свой инструмент ещё не видела. Всё было разобрано по кускам — струны, подставка… Конечно, играть надо. Сделали маленькую паузу в концерте. Оркестранты начали мне приносить свои инструменты. К сожалению, как всегда в провинции, ни одного порядочного инструмента там не оказалось. Я схватила какой-то инструмент, начала для пробы каденцию брамсовского концерта, забыв что у меня под руками не «Гвадонини». Раздался совершенно дикий треск, я просто не понимала, что я играю. Минут пять я поиграла, как-то приспособилась, и пришлось сыграть концерт на этом инструменте.
И совсем уже комический случай. Однажды мы с Евгением Малининым ехали в поезде на гастроли. Чтобы мы могли нормально отдохнуть в дороге, нам взяли отдельное 4-х местное купе. Я в первый раз законно (билет был куплен!) положила свою виолончель на верхнюю полку. Входит проводница и спрашивает: «Бельё будете брать?». «Конечно». Малинин подает ей деньги за два комплекта белья, после чего она, глядя на мой «саркофаг», говорит: «А что, он не будет брать бельё?» и добавляет: «Ну ладно, пусть едет как хочет». »