Родился 23 ноября 1948 года в городе Горьком (РСФСР).
В 1951 году с семьёй переехал в Запорожье.
В 1966 году окончил среднюю школу (с золотой медалью), а в 1971 — Запорожский машиностроительный институт им. В. Я. Чубаря.
С сентября 1971 работал на Запорожском трансформаторном заводе (инженер-конструктор, старший инженер, социолог), с 1976 — старшим мастером в ПТУ, преподаватель специальных дисциплин.
С 1986 — методист Дворца культуры металлургов в Запорожье. Параллельно занимался творческой деятельностью, выпустил несколько поэтических сборников и в 1987 году вступил в Союз писателей СССР.
В 1988—1992 возглавлял Запорожское областное литературное объединение, затем — на журналистской работе (в 1991—1998 — корреспондент местной газеты «Наш город» ). Был членом КПСС.
В марте 1990 года принял участие в учредительной конференции первой на Украине организации российских соотечественников — Украинском обществе русской культуры «Русь» , был избран в состав правления и в апреле 1992 возглавил Запорожскую областную организацию «Руси» . Вёл жёсткую борьбу с украинскими националистами и чиновниками как публицист и общественный лидер. За это подвергался преследованиям, в 1999 был исключён из Союза писателей Украины с формулировкой: «антиконституционная деятельность, направленная на ликвидацию государственной независимости Украины» . Через суд добился отмены этого акта, но возвращаться в «Національну спілку письменників» не стал, вступив в Союз писателей России.
В 1994—1998 годах — депутат Запорожского областного совета. Примкнул к Партии славянского единства, возглавляя её Запорожскую региональную организацию.
В мае 1996 года на «3 съезде» был избран председателем ПСЕ, но прежний руководитель партии Игорь Карпенко не признал легитимности этого съезда.
В июле 1997 года Баулин уступил пост председателя ПСЕ Виктору Шестакову, оставшись членом Политсовета.
В 1998 избран в Верховную Раду Украины по 76 мажоритарному избирательному округу г. Запорожья.
В парламенте 3 созыва активно выступал в поддержку русского языка и сближения с Россией.
В январе 2001 г. выступил инициатором создания межфракционного депутатского объединения ЗУБР (За союз Украины, Белоруссии и России); становится координатором ЗУБРа, объединившего 126 народных депутатов Украины. Летом 2001 совместно с Н. Витренко участвовал в создании межпарламентского объединения ЗУБР депутатов Государственной Думы Российской Федерации, Национального Собрания Республики Беларусь и Верховной Рады Украины.После проигрыша выборов 2002 года вступил в Русское движение Украины А.Свистунова, стал заместителем председателя партии «Русский блок» и руководителем идеологического отдела РБ.
С ноября 2002 шеф-редактор партийной газеты «Русская правда» . Затем сблизился с ПСПУ и осенью 2004 перешёл туда. Во время президентской кампании 2004 — доверенное лицо кандидата в президенты Украины Н. Витренко.
В 2005—2006 гг. возглавлял Луганский, а затем Запорожский обкомы ПСПУ.
На парламентских выборах 2006 и 2007 гг — 3-й номер списка Блока Наталии Витренко «Народная оппозиция» .
С апреля 2006 года — депутат Запорожского городского совета, руководитель фракции «Народной оппозиции» .28 октября 2006 года на Учредительном съезде Партии «Киевская Русь» был избран её председателем. Переизбран на 3 съезде партии в декабре 2009 года. 1 декабря 2008 года в качестве министра иностранных дел вошёл в состав оппозиционного «Правительства народного спасения» , возглавляемого Наталией Витренко.28 марта 2009 года президиум Всеукраинского объединения русских соотечественников избрал его председателем ВОРСа.2 марта 2013 года Павел Баулин добровольно сложил с себя полномочия председателя Партии «Киевская Русь» .