С начала 1960-х годов Новелла Матвеева занималась переводами с языков народов СССР и стран соцлагеря: чеченского (Мусбек Кибиев), карачаево-балкарского (Халимат Байрамукова), армянского (Ашот Граши), молдавского (Анатол Кодру), калмыцкого (Бося Сангаджиева, Давид Кугультинов), чешского (Константин Библ). Переводила итальянского поэта эпохи Возрождения Гаспара Стампа, греческого поэта и писателя Костиса Паламаса.

Широкую известность принесли поэту песни собственного сочинения, с которыми Н. Н. Матвеева выступала с конца 50-х. Новелла Матвеева стояла у истоков бардовской песни. По словам Булата Окуджавы, она первая взяла в руки гитару. При этом себя автор предпочитала называть себя «менестрелем» или «полигимником» (по имени музы Полигимнии). Л. З. Лунгина вспоминала, что Н. Н. Матвеева ничем не напоминала «обычную» певицу: «…пела резким, плохо поставленным голосом. (…) Полная, страдавшая хроническим головокружением, не сказать что красивая молодая женщина. Но стоило ей взять гитару и запеть — и слушатели были полностью в ее власти. Она как-то умела обнаружить скрытый лиризм самых обычных вещей. Двери официальной литературы были перед ней закрыты, но ее нонконформизм открыл ей сердца всех, кто ее слушал» («Подстрочник»).

Е. А. Евтушенко позднее напишет о Новелле Матвеевой: «Она волшебно поет тоненьким, девчоночьим голосом свои песни под гитару, и, чем больше я старею, тем все больше люблю эти песни» (Строфы века. Антология русской поэзии, 1995). Не имея музыкального образования и не зная нотной грамоты, Новелла Матвеева записывала мелодии, рисуя гриф и помечая на нем аккорды.

Пластинка «Песни Новеллы Матвеевой», вышедшая в 1966 году и затем не раз переизданная, стала первой записью авторской песни в Советском Союзе. Песни с этой пластинки — «Караван», «Девушка из харчевни», «Цыганка-молдаванка», «Кораблик», «Капитаны без усов» и другие — стали любимыми песнями молодежи.