Один из ведущих представителей российского наивного искусства. Стиль Леонова характеризуется сочетанием больших и малых фигур, а также разбиением плоскости картины на отдельные квадратики-«телевизоры», в которых разворачиваются различные сцены. В 1984 году имя Павла Леонова вошло во Всемирную энциклопедию искусства. В конце 1930-х годов уехал в город на заработки. За свою жизнь сменил множество профессий. Работал на заводах, рубил лес, ремонтировал суда, строил дороги, был столяром, штукатуром, печником, жестянщиком, маляром, художником-оформителем. Жил в Орле, в Украине, в Азербайджане, Грузии, Узбекистане.
Был несколько раз арестован в 1940–1950 годах. Живописью стал пробовать заниматься в 1950-е годы на Камчатке. В 1960-е участвовал в работе Заочного народного университета искусств (ЗНУИ), где его учителем был Рогинский. В 1980-е он бросил живопись, так как боялся ареста за нетрудовые доходы. С 1990-х годов начался наиболее плодотворный период его творчества, когда его работы стали покупать коллекционеры. Он жил всегда в перевёрнутом мире, в Зазеркалье, в котором есть всё — свои законы, своё небо, своя земля.
В 1997 году получил Гран при на Международной выставке наивного искусства «INSITA» в Братиславе (Словакия). В 2000 году получил Гран при на 6-м Интернациональном конкурсе наивного искусства «Gallerie pro art Kasper» в Швейцарии.
Персональные выставки
1993 Сон Золотой. Центр современного искусства на Якиманке, Москва
2005 Павел Леонов. Московский музей современного искусства, Москва
2010 Павел Леонов (Из собр. К. Богемской и А. Турчина). Галерея Роза Азора, Москва
2011 Живопись Павла Леонова из собрания К. Г. Богемской. Отдел личных коллекций ГМИИ имени А. С. Пушкина, Москва
2012 Рисунок и живопись. Галерея Роза Азора, Москва
Коллекции
Владимиро-Суздальский музей-заповедник
Галерея современного искусства ARTSTORY, Москва
Музей наивного искусства, Москва
Музей органической культуры, Коломна
Музей Царицыно, Москва
Музей Шарлотты Цандер, Германия
Современная галерея, Загреб, Хорватия