Павел Виноградов родился 31 августа 1953 года в городе Магадан. Рос в семье инженера. Детство провёл в городе Анадырь Чукотского автономного округа, там же окончил среднюю школу в 1970 году.
В 1970 году приехал в Москву и пытался поступить в Московский авиационный институт имени Серго Орджоникидзе, но неудачно. С сентября 1970 года работал токарем в МАИ, с октября 1970 года токарем на Московском машиностроительном заводе "Красный Октябрь". В 1971 году вновь поступал в МАИ, на этот раз успешно.
В 1977 году окончил Московский авиационный институт. Во время учёбы работал в студенческом КБ "Искра", а также старшим лаборантом на одной из кафедр МАИ и в Отраслевой научно-исследовательской лаборатории МАИ. С апреля 1977 года - инженер, с мая 1978 года - старший инженер МАИ в отраслевой лаборатории "Системы автоматизированного проектирования летательных аппаратов". В 1980 году окончил заочное отделение МАИ по специальности "Системный анализ, большие компьютерные системы".
С августа 1983 года работал в НПО "Энергия": инженер, с августа 1985 года - старший инженер, с января 1989 года - ведущий инженер, с февраля 1989 года - начальник группы, с ноября 1989 года - начальник сектора 292-го отдела. Занимался отработкой действий экипажей КК "Союз ТМ" и орбитального комплекса "Буран", разработкой автоматизированных систем подготовки космонавтов. Участвовал в подготовке пусков космических кораблей, в 1985 году принимал участие в подготовке группы бортинженеров по программе "Буран".
С мая 1992 года - в отряде космонавтов НПО "Энергия", космонавт-испытатель.
5 августа 1997 года - 19 февраля 1998 года совершил свой первый космический полёт в качестве бортинженера космического корабля "Союз ТМ-26" и орбитального научно-исследовательского комплекса "Мир", продолжительностью 197 суток 17,5 часов. За время полёта совершил 5 выходов в открытый космос общей продолжительностью 26 часов 19 минут.
За успешное осуществление космического полёта и проявленные при этом мужество и героизм Виноградову Павлу Владимировичу Указом Президента Российской Федерации от 10 апреля 1998 года присвоено звание Героя Российской Федерации.
С февраля 2003 года - командир отряда космонавтов - начальник 291-го отдела РКК "Энергия".
Второй космический полёт совершил с 30 марта по 29 сентября 2006 года - командир экипажа КК "Союз ТМА-8" и 13-й основной экспедиции Международной космической станции совместно с американским астронавтом Джеффри Уильямсом и 1-м бразильским астронавтом Маркусом Понтесом. С июля 2006 года в составе экспедиции работал также астронавт США второй бортинженер Томар Райтер. После успешного выполнения программы экспедиции 29 сентября 2006 года вернулся на Землю в спускаемом аппарате КК "Союз ТМА-8" с Джеффри Уильямсом и участницей экспедиции посещения первой женщиной-космическим туристом Анюше Ансари. В этом полёте выполнил 1 выход в открытый космос.
С октября 2007 года - заместитель начальника Лётно-космического центра РКК "Энергия".
Третий космический полёт Виноградова начался 28 марта 2013 года. Стартовал на КК "СоюзТМА-08М", командир корабля и командир 35/36-й основных экспедиций на МКС. В составе стартового экипажа находились космонавт России Александр Мисуркин и астронавт США Кристофер Кэссиди. Полёт во многом уникальный: впервые в мире экипаж выполнил доставку на МКС за 6 часов, а во-вторых, в этом полёте Павел Виноградов стал самым пожилым космонавтом России, стартовавшим в космос в возрасте 59 лет. Космический полёт завершился 11 сентября 2013 года. Его продолжительность составила 166 суток 6 часов 15 минут. Во время полёта выполнил 1 выход в открытый космос.
Всего за три полёта имеет общий срок пребывания на орбите в 546 суток 22 часа 32 минуты и 7 выходов в открытый космос.
Живёт в Москве. Продолжает работу в отряде космонавтов. С 1999 года – вице-президент Федерации космонавтики РФ.
Награждён орденами «За заслуги перед Отечеством» 4-й степени, Мужества, медалями, в том числе «За заслуги в освоении космоса», а также иностранными наградами, в том числе 2 медалями «За космический полёт».