Сначала занималась одиночным катанием у Виктора Николаевича Кудрявцева. Позже, спортсменку пригласила к себе в группу Татьяна Тарасова, поставив в пару с Василием Благовым. Дебют пары был удачным: на турнире на приз газеты «Московские новости» они были вторыми, затем выиграли Кубок Европы, а накануне чемпионата СССР разболелись и заняли только четвертое место. Тогда Татьяна Тарасова предложила Наталье поменять партнера, но пришлось бы отнимать его у подруги, на что она не пошла и завершила карьеру. Спустя некоторое время получила приглашение от Тамары Москвиной тренировать молодежь.
КУБОК СССР
Свою тренерскую карьеру Наталья Павлова начала в качестве помощницы Тамары Москвиной. После конфликта с Москвиной, Наталья Евгеньевна начала тренировать спортсменов самостоятельно. Именно к ней в 1993 году обратились чемпионы Европы Марина Ельцова и Андрей Бушков, решившие уйти из группы Москвиных, когда те начали настаивать на переходе пары в профессионалы, так как не видели перспектив у спортсменов в любителях. Вопреки ожиданиям новообразованный квартет (с Павловой работала хореограф Светлана Король, выполняющая попутно функции второго тренера, психолога и делавшая множество других полезных дел) не пошел под откос, а в 1996 году победил на чемпионате мира. В 1997 последовали европейское «золото» и «серебро» на первенстве мира. После неудачи на Олимпиаде Бушков и Ельцова решили прервать совместные выступления. Тогда Павлова сосредоточилась на работе со своими молодыми спортсменами Тотьмяниной и Марининым. Когда новая пара прочно закрепилась в сборной и стала вторым номером страны вслед за Бережной и Сихарулидзе, в группу к Павловой вернулись Бушков/Ельцова. Их появление не обрадовало Маринина и Тотьмянину, которые, посчитав что приоритет у тренера будет у титулованных Бушкова и Ельцовой, решили уйти от Натальи Евгеньевны к Москвиной. В конечном итоге переход состоялся, но не к Москвиной, спортсмены ушли к начинающему тренеру Олегу Васильеву.
Осенью 2006 года Наталья Павлова по личному приглашению президента Федерации фигурного катания Москвы, префекта Северо-Восточного административного округа столицы Ирины Рабер переехала в Москву, где тренирует на катке «Синяя птица». Среди её учеников Любовь Илюшечкина и Нодари Маисурадзе, Анастасия Мартюшева и Алексей Рогонов, Татьяна Данилова и Андрей Новосёлов.
Вдова советского баскетболиста Юрия Павлова, имеет дочь Анастасию, которая работает вместе с матерью.
Северо-Западный заочный политехничекий институт (1979).