Родился будущий священномученик 17 июня 1877 года в рязанском селе Поляны, в семье священника Николая Добромыслова. Он окончил Рязанское духовное училище, затем семинарию, а в 1901 году — Московскую духовную академию. Тогда же он женился на Клавдии Алексеевне Шуваловой, дочери управляющего помещичьим имением; в семье родилось шестеро детей.

Во священника его рукоположил 1 октября 1901 года епископ Рязанский и Зарайский Полиевкт — к Старо-Ямской Николаевской церкви в Рязани. Дальше пошли годы преподавания: епархиальное женское училище, мужская частная гимназия, Мариинская женская гимназия, где он был и заведующим, и законоучителем. Он состоял в епархиальном миссионерском комитете и в отделении училищного совета. В 1913 году был награждён наперсным крестом, а в 1914-м назначен к Скорбященской церкви при рязанской богадельне.

В 1918 году его арестовали как заложника — только потому, что он был известным в городе священником, — и какое-то время держали в московской тюрьме. В 1923 году отца Павла определили в Благовещенскую церковь Рязани и возвели в сан протоиерея, а в марте 1924 года архиепископ Борис назначил его уездным благочинным.

Обновленческий раскол он не принял и по поручению архиепископа написал историю обновленчества в Рязанской епархии. В письмах владыке он пересказывал городские сцены: как обновленцы через милицию и губисполком пытались отбирать храмы, как на их праздник в кафедральном соборе собралось десятка три любопытствующих. Свой довод он повторял и в лицо: если у вас истина, народ придёт сам, а у нас никого не принуждают.

В 1926 году Особое Совещание при коллегии ОГПУ приговорило его к трём годам концлагеря; когда на Белом море открылась навигация, его отправили на Соловки. Вернувшись, он снова служил в Рязанской епархии, но в 1930 году был арестован опять и получил три года ссылки, которую отбывал в Семипалатинске. В 1933 году он вернулся и служил в Благовещенском храме, а когда часть причта ушла в обновленчество, был назначен настоятелем Казанского храма села Солотча.

26 марта 1938 года отца Павла арестовали и заключили в рязанскую тюрьму. Полтора месяца шли допросы: следователь требовал признать участие в «контрреволюционной организации церковников» и в антисоветской агитации. Священник отвечал одно и то же — в такой организации не состоял, агитации не вёл, а характеризовать политические взгляды своих знакомых не может, потому что о политике с ними не разговаривал. 29 мая 1938 года его приговорили к восьми годам исправительно-трудового лагеря.

В Карагандинский лагерь он прибыл 16 июля того же года. Протоиерей Павел Добромыслов скончался там 2 февраля 1940 года и был погребён в безвестной могиле.

Священномучеников на иконах принято писать в священническом облачении, с крестом в руках. Память совершается 2 февраля, 7 февраля и 23 июня.