Родился 25 октября 1946 г. в г. Шахунья Горьковской области (ныне Нижегородская обл.) в семье инженера-строителя. Вскоре после его рождения семья переехала в г. Кызыл Тувинской АССР.
В 1972 г. окончил экономический факультет Ульяновского сельскохозяйственного института (ныне Ульяновский государственный аграрный университет им. П. А. Столыпина), в 1985 г. - Хабаровскую Высшую партийную школу.
В 2003 г. в Институте социально-политических исследований РАН защитил диссертацию на соискание степени кандидата политических наук по теме "Приоритетные направления укрепления российской государственности на пути к консолидации общества".
Доктор политических наук. В 2008 г. в Институте социально-политических исследований РАН защитил диссертацию на тему "Социально-политическая стабильность – основное условие развития России".
В 1964-1965 гг. работал учеником токаря на Московском заводе деревообрабатывающих станков и автоматических линий.
В 1966 г. - старший механик Всесоюзного института механизации сельского хозяйства "ВИМ" (Москва).
В 1972-1973 гг. был ассистентом кафедры бухгалтерского учета и экономической статистики Ульяновского сельскохозяйственного института.
С 1973 по 1977 г. - экономист, старший экономист-нормировщик, начальник строительно-монтажного управления Верхне-Индигирской геологоразведочной экспедиции Якутского геологического управления.
В 1975 г. вступил в Коммунистическую партию Советского Союза (КПСС).
В 1977-1983 гг. - начальник отдела, заместитель генерального директора производственно-геологического объединения "Якутскгеология", был экономистом участка, начальником отдела капитального строительства, последняя должность - заместитель генерального директора.
С 1983 г. по 1985 г. – инструктор Якутского городского комитета (горкома) КПСС.
В 1985-1987 гг. - второй секретарь Вилюйского районного комитета (райкома) КПСС (Якутская АССР).
В 1987-1988 гг. - председатель Вилюйского районного исполнительного комитета (исполкома) Советов народных депутатов.
С 1988 г. по 1990 г. занимал пост председателя исполкома Якутского городского Совета народных депутатов (фактически – мэр города).
В 1990-1993 гг. - председатель Якутского горсовета народных депутатов, мэр г. Якутска.
В 1990-1993 гг. был народным депутатом Якутского городского совета и народным депутатом РСФСР. В мае 1991 г. в входил в депутатскую группу "Отчизна", с 1993 г. входил во фракцию "Согласие ради прогресса", был членом комитета Верховного совета РСФСР по делам женщин, охраны семьи, материнства и детства. На съезде народных депутатов познакомился с Александром Коржаковым, руководителем охраны президента РСФСР Бориса Ельцина.
1 апреля 1993 г. был назначен первым заместителем Федора Морщакова - начальника Главного социально-производственного управления Администрации президента РФ.
С 20 августа - и. о. начальника, с 15 сентября 1993 г. по 15 ноября 1993 г. - начальник Главного социально-производственного управления Администрации президента РФ.
В ноябре 1993 г. распоряжением президента РФ Бориса Ельцина Главное социально-производственное управление Администрации президента было преобразовано в новую, самостоятельную структуру федерального уровня - Управление делами президента РФ. При участии Бородина функции и полномочия ведомства были значительно расширены. В компетенцию Управделами были включены финансовое, материально-техническое и социально-бытовое обеспечение Администрации президента, правительства, Федерального собрания, Конституционного, Высшего арбитражного и Верховного судов.
С 15 ноября 1993 г. по 10 января 2000 г. занимал должность управляющего делами президента РФ (в этот период пост главы государства занимали Борис Ельцин, с 31 декабря 1999 г. – Владимир Путин).
С августа 1996 г. по март 1997 г. заместителем Павла Бородина в Управлении делами президента РФ был Владимир Путин.
17 декабря 1995 г. баллотировался на выборах в Государственную думу РФ II созыва по общефедеральному списку "Блока Ивана Рыбкина". В парламент не прошел, так как блок не преодолел 5-процентный барьер.
С сентября 1997 г. по декабрь 1998 г. – член Межведомственной комиссии Совета безопасности РФ по экономической безопасности.
В 1998 г. генеральный прокурор РФ Юрий Скуратов возбудил в отношении ряда высокопоставленных российских чиновников, включая Павла Бородина, уголовное дело по подозрению в получении взяток от руководителя швейцарской строительной компании "Мабетекс" Беджета Паколли за предоставление подрядов на реставрацию Кремля. В то же время расследование в отношении "Мабетекс" велось в прокуратуре Швейцарии. В апреле 2000 г. генпрокурор Юрий Скуратов был отстранен от должности. 18 декабря 2000 г. уголовное дело в отношении Павла Бородина в России было прекращено "за отсутствием состава преступления".
19 декабря 1999 г. выставил свою кандидатуру на выборах мэра Москвы. Занял третье место из восьми кандидатов, набрав 6,01% голосов избирателей. На выборах победил действующий градоначальник Юрий Лужков (69,89%), второе место занял лидер Союза правых сил Сергей Кириенко (11,25%).
26 января 2000 г. был назначен государственным секретарем Союзного государства России и Белоруссии. Эта должность была введена договором о создании Союзного государства от 8 декабря 1999 г. Занимал пост до 25 ноября 2011 г.
В январе 2000 г. швейцарская прокуратура выдала международный ордер на арест Бородина по делу "Мабетекс", а также по обвинению в незаконном отмывании денег в период пребывания на посту управляющего делами президента Бориса Ельцина. 17 января 2001 г. он был арестован в аэропорту им. Дж.Ф. Кеннеди в Нью-Йорке (США). 7 апреля 2001 г. экстрадирован в Швейцарию. 12 апреля того же года обвинительная палата Женевы вынесла постановление об освобождении Бородина под залог в сумме 5 млн швейцарских франков (2,9 млн долларов США) с обязательством являться по вызову следственного судьи. После внесения генеральным консулом России в Женеве указанного залога Бородин 13 апреля возвратился в Москву. 6 марта 2002 г. прокуратура Женевы (признала экс-чиновника виновным в отмывании 38 млн швейцарских франков (22,4 млн. долларов) и наложила на него штраф (законы Швейцарии разрешали обвинению налагать наказания без решения суда) в размере 300 тыс. франков (175 тыс. долларов).
На выборах в Госдуму РФ IV созыва 7 декабря 2003 г. возглавлял список избирательного блока "Великая Россия - Евразийский союз". В Думу не прошел, так как объединение не преодолело 5-процентный барьер.
С февраля 2012 г. по май 2014 г. являлся председателем комитета по этике Российского футбольного союза.
В 2013 г. указом президента РФ Владимира Путина "за особые заслуги перед Российской Федерацией и большой вклад в развитие и укрепление российско-белорусских отношений" Павлу Бородину было установлено "дополнительное ежемесячное материальное обеспечение". Кроме того, вместе с членами семьи за ним было сохранено "санаторно-курортное обслуживание, которое ему предоставлялось на день прекращения полномочий по должности государственного секретаря Союзного государства".
С 2014 г. по настоящее время - председатель правления Союза предпринимателей евразийского экономического пространства "Деловой союз Евразии".
Также руководит отделом геоэкономических и геополитических исследований Евразии Центра политологии Института социально-политических исследований Федерального научно-исследовательского социологического центра РАН.
Являлся членом совета директоров Общественного российского телевидения (ОРТ; 1996-1998), наблюдательного совета компании "Алроса" (с 1998 г.).
Был президентом баскетбольного клуба "Евраз" (Екатеринбург; с 2003 г.), футбольного клуба "Торпедо".
Входит в попечительский совет Московской городской организации Всероссийского физкультурно-спортивного общества "Динамо".
Действительный государственный советник РФ I класса (1996).
Награжден орденами "За заслуги перед Отечеством" II и IV степеней (1996; 2016), Почета (2011). Имеет ордена Белоруссии - Франциска Скорины (2001), Дружбы народов (2006), Отечества III степени (2011).
Отмечен благодарностями президента РФ (1995, 1996, 2006), Почетными грамотами правительства РФ (1996, 2006).
Женат. Супруга - Валентина Александровна (девичья фамилия Чудинова). Закончила юридический факультет Казанского университета, в Якутии руководила детдомами, с 1996 г. стала основательницей и главой благотворительного фонда "Отчий дом". Родная дочь – Екатерина Силецкая (род. 1970). Четверо приемных детей: Сергей, Петр, Иван, Наталья.