Родился 29 июня 1947 года в селе Сусанино Костромской области в многодетной семье. Отец и мать — Павлин Николаевич и Екатерина Ивановна — работали в Москве на заводе шлифизделий. По данным СМИ, дед-крестьянин назвал сына Павлином в честь святого — в РПЦ насчитывается два "обычных" святых с таким именем и два Павлина-новомученика.
До семи лет жил в Костромской области, затем переехал к родителям в Москву, где окончил восемь классов школы #743. В 1966 году окончил Московский авиационный техникум и ушел в армию, служил на Сахалине авиамехаником войск ПВО. С 1968 по 1975 год работал на радиозаводе "Салют" в Москве помощником мастера, начальником бюро подготовки производства, старшим инженером-технологом, секретарем комитета комсомола. В 1971 году окончил вечернее отделение Московского института радиотехники, электроники и автоматики по специальности "радиоинженер", позднее — Академию народного хозяйства. В 1971 году вступил в КПСС и с 1975 года работал в партийных органах — заместителем секретаря парткома завода "Салют"; инструктором, заместителем заведующего промышленно-транспортным отделом Перовского райкома КПСС; инструктором Московского горкома КПСС. С 1980 года — заместитель заведующего отделом машиностроения МГК КПСС (горком возглавлял Борис Ельцин). С 1986 года — председатель райисполкома, первый секретарь райкома КПСС, председатель райсовета Перовского района Москвы. В 1990-1991 годах — секретарь МГК КПСС. С 1987 по 1993 год избирался депутатом Моссовета. Весной 1991 года потребовал отставки председателя Моссовета Гавриила Попова за "агитацию в ходе кампании по выдвижению кандидатов в мэры Москвы". С августа 1991 года — коммерческий директор хоккейного клуба "Динамо", одновременно первый зампред исполкома московской организации КПРФ. В июле 1994 года назначен префектом Южного административного округа Москвы. Весной 1996 года баллотировался в вице-мэры Москвы в паре с Юрием Лужковым. 7 июня 1996 года на Валерия Шанцева совершено покушение: возле его подъезда сработало взрывное устройство. 16 июня избран вице-мэром Москвы, руководил социальной сферой. 19 декабря 1999 года повторно избран вице-мэром, руководил комплексом экономической политики и развития города. В январе 2000 года стал первым вице-премьером правительства города.
Награжден орденом "Знак почета". Заслуженный работник ЖКХ, почетный строитель Москвы. Академик Международной академии информатизации, почетный доктор Государственного университета управления. Президент Федерации хоккея и Федерации бильярда Москвы, член правления и председатель попечительского совета хоккейного клуба "Динамо".
Любит баню, рыбалку, теннис, футбол, домино.Супруга Татьяна — зампред регионального отделения ФКЦБ в ЦФО. Дочь Светлана — преподаватель физики, сын Александр работает в ресторанном бизнесе.