Родилась 6 сентября 1945 г. в Куйбышеве (ныне Самара) в семье военнослужащего.
В 1970 г. окончила исторический факультет Ленинградского государственного университета им. А. А. Жданова (ныне - Санкт-Петербургский государственный университет) по специальности "историк-археолог".
После окончания вуза работала в Саяно-Тувинской экспедиции Института археологии Академии наук СССР, затем — старшим консультантом Ленинградского отделения Всероссийского общества охраны памятников истории и культуры (отвечала за молодежную секцию). Была старшим хранителем филиала Шлисельбургской крепости "Орешек", Музея истории Ленинграда.
В 1979 г. возглавила областную инспекцию охраны памятников Леноблисполкома.
С ноября 1987 г. по 28 августа 1997 г. - директор Государственного музея истории Санкт-Петербурга. Была одним из инициаторов захоронения праха великого князя Владимира Кирилловича в Петропавловском соборе, а также установки памятника Петру I работы Михаила Шемякина на территории музея.
В 1997-1998 гг. - министр культуры РФ в правительствах Виктора Черномырдина и Сергея Кириенко. Была назначена 28 августа 1997 г. указом президента РФ Бориса Ельцина, вышла в отставку 23 августа 1998 г. вместе со всем правительством РФ (после дефолта 17 августа 1998 г.).
30 сентября 1998 г. вернулась в Министерство культуры РФ в качестве первого заместителя главы ведомства. Министерство в 1998-2000 гг. возглавлял Владимир Егоров, в 2000-2004 гг. - Михаил Швыдкой. Наталия Дементьева занимала пост до апреля 2004 г. (Минкультуры было упразднено, вместо него образовано Федеральное агентство по культуре и кинематографии).
В 2014-2019 гг. - член Совета Федерации РФ, представитель Госсобрания Республики Марий Эл.
10 июня 2004 г. Государственное собрание Республики Марий Эл наделило Наталию Дементьеву полномочиями члена Совета Федерации РФ, представителя от законодательного органа государственной власти Марий Эл (ее полномочия в Совфеде были подтверждены 23 июня того же года). C июля 2004 г. по ноябрь 2011 г. входила в комитет СФ по бюджету, с ноября 2011 г. была членом комитета по бюджету и финансовым рынкам. Входила в комиссии по делам молодежи и спорту, по делам молодежи и туризму, по физической культуре, спорту и развитию олимпийского движения, по информационной политике.
14 сентября 2014 г. была избрана депутатом Государственного собрания Республики Марий Эл VI созыва. Баллотировалась по списку регионального отделения партии "Единая Россия" (возглавляла региональную группу №18). После избрания вновь была наделена полномочиями члена Совета Федерации.
Сложила полномочия сенатора в октябре 2019 г. В Совете Федерации ее сменил Сергей Мартынов.
Награждена орденом Дружбы (2015). Имеет благодарность президента (2014) и правительства РФ (2018).
Заслуженный работник культуры РФ (1996).
Лауреат Национальной премии общественного признания достижений женщин "Олимпия" Российской академии бизнеса и предпринимательства в 2001 г.