Родился 31 августа 1953 г. в Магадане. Детство и школьные годы будущего космонавта прошли в гор. Анадыре (Чукотский национальный округ в составе Магаданской обл., ныне Чукотский автономный округ). Павел Виноградов неоднократно становился призером физико-математических олимпиад Анадыря.
Образование
В 1977 г. окончил Московский авиационный институт (ныне МАИ имеет статус национального исследовательского университета) по специальности "производство летальных аппаратов" с присвоением квалификации инженера-механика. В 1980 г. на заочном отделении МАИ получил специальность "системный анализ, большие компьютерные системы".
Начало трудовой деятельности
С сентября 1970 г., после неудачной попытки поступить в МАИ, работал учеником токаря, затем токарем II разряда на Московском машиностроительном заводе "Красный Октябрь".
В 1970-е гг. учебу в МАИ сочетал с работой в студенческом конструкторском бюро "Искра" и отраслевой научно-исследовательской лаборатории (ОНИЛ) вуза, где был старшим лаборантом.
В 1977-1978 гг. - инженер, в 1978-1983 гг. - старший инженер ОНИЛ МАИ. Занимался разработкой программных средств для автоматизированных интерактивных систем проектирования космических летательных аппаратов (ЛА) многократного использования, созданием расчетных моделей аэродинамики и компоновки ЛА, компьютерной графикой. Одновременно был нештатным испытателем Института медико-биологических проблем Академии наук СССР (ныне ИМБП РАН).
Работа в НПО "Энергия"
В августе 1983 г. Павел Виноградов перешел на работу в НПО "Энергия" (с 1994 г. по н. в. - Ракетно-космическая корпорация "Энергия" им. С. П. Королева), находящееся в подмосковном гор. Калининграде (ныне Королев). Сначала был инженером, с августа 1985 г. - старшим инженером, с января 1989 г. - ведущим инженером, с февраля 1989 г. - начальником группы, с ноября 1989 г. - начальником сектора 292-го отдела. Занимался отработкой действий экипажей космических кораблей "Союз ТМ" и "Буран", а также разработкой автоматизированных систем подготовки космонавтов.
В отряде космонавтов
Павел Виноградов неоднократно пытался попасть в отряд космонавтов НПО "Энергия". В первый раз подал заявление в 1981 г., но в отряд принят не был, так как не являлся сотрудником предприятия.
13 мая 1992 г. он был зачислен кандидатом в космонавты-испытатели НПО "Энергия" в рамках 11-го набора. 10 мая 1995 г. был переведен на должность космонавта-испытателя 291-го отдела (отряда космонавтов) РКК "Энергия". Впоследствии был назначен инструктором-космонавтом-испытателем.
5 августа 1997 г. - 19 февраля 1998 г. Павел Виноградов совершил свой первый полет в космос в качестве бортинженера корабля "Союз ТМ-26" и 24-й основной экспедиции на орбитальный комплекс "Мир" вместе с Анатолием Соловьевым (командир). Экипажу пришлось заниматься ремонтом разгерметизированного модуля "Спектр" космической станции, который получил серьезные повреждения в июне 1997 г. при перестыковке грузового корабля "Прогресс М-34". За время экспедиции Павел Виноградов пять раз выходил в открытый космос.
С февраля 2003 г. по октябрь 2007 г. - командир отряда космонавтов (начальник 291-го отдела) РКК "Энергия". Одновременно являлся инструктором-космонавтом-испытателем.
В ходе второго полета, с 30 марта по 29 сентября 2006 г., был командиром корабля "Союз ТМА-8" и 13-й основной экспедиции на Международную космическую станцию (МКС). Работал на МКС с американцем Джеффри Уилльямсом и немцем Томасом Райтером (прибыл на станцию в июле 2006 г. на шаттле Discovery), а также с первым космонавтом Бразилии Маркусом Понтесом (член 10-й экспедиции посещения МКС). Павел Виноградов участвовал в одном выходе в открытый космос.
В октябре 2007 г. был назначен заместителем начальника летно-космического центра РКК "Энергия".
29 марта - 11 сентября 2013 г. был командиром корабля "Союз ТМА-08М", бортинженером экспедиции МКС-35 и командиром МКС-36. Работал на Международной космической станции с Александром Мисуркиным и американским астронавтом Кристофером Кэссиди. 19 апреля Павел Виноградов, которому на тот момент было 59 лет, выполнил выход в открытый космос. Таким образом, он стал самым старшим по возрасту человеком, вышедшим в открытое космическое пространство (побил прежний рекорд американца Стори Масгрейва, совершившего выход в 58-летнем возрасте 9 декабря 1993 г. с борта шаттла Endeavour).
По данным Центра подготовки космонавтов им. Ю. А. Гагарина, в общей сложности за три орбитальных полета Павел Виноградов провел в космосе 546 дней 22 часа 33 минуты, осуществил семь выходов в открытый космос суммарной продолжительностью 38 часов 27 минут.
Числился в отряде космонавтов до 2017 г., имел квалификацию инструктора-космонавта-испытателя I класса.
Преподавательская, общественная и политическая деятельность
Заведовал кафедрой С-16 "Интегрированные бортовые комплексы навигации управления и наведения ЛА" филиала "Стрела" МАИ в подмосковном гор. Жуковском.
В марте 1999 г. был избран вице-президентом Федерации космонавтики России.
В 2003 и 2009 гг. избирался депутатом муниципального собрания района "Рязанский" (впоследствии внутригородское муниципальное образование "Рязанское") Юго-Восточного административного округа гор. Москвы.
7 декабря 2003 г. баллотировался в Государственную думу РФ IV созыва от Народной партии РФ, но депутатом избран не был.
11 октября 2009 г. участвовал в выборах в Московскую городскую думу от регионального отделения партии "Единая Россия". По итогам распределения мандатов в Мосгордуму не прошел.
Награды, почетные звания
Герой Российской Федерации (1998).
Награжден орденами "За заслуги перед Отечеством" IV степени (2008), Мужества (2015), медалью "За заслуги в освоении космоса" (2011).
Имеет две медали НАСА "За космический полет" (1998, 2007).
Летчик-космонавт РФ (1998). Почетный гражданин Анадыря (2006) и Магаданской области (2013).