Происхождение — из бедных дворян, вероисповедание — православный. С 12 лет учился за казённый счёт в Нижегородском графа Аракчеева кадетском корпусе, по окончании которого стал юнкером московского Александровского военного училища. Окончил учёбу в 1892 году, в звании подпоручика был направлен в лейб-гвардии Московский полк. В 1897 году поступил в Академию Генерального штаба, которую окончил с отличием в 1900 году. Произведён в штабс-капитаны и причислен к Генеральному штабу. Благодаря своим способностям сделал блестящую карьеру, к 1914 году являлся уже полковником и занимал должность начальника 12-го Управления Генерального штаба. В годы Первой мировой войны 1914—1918 — начальник оперативного отдела генерал-квартирмейстера штаба Юго-Западного фронта, начальник штаба 3-й армии, генерал для поручений при ГК армиями Юго-Западного фронта, помощник генерал-квартирмейстера штаба Северо-Западного фронта, генерал-квартирмейстер штаба Западного фронта. В 1915 году произведён в генерал-майоры. В декабре 1917 года уволен в отставку.
В 1918 году отказался примкнуть к белому движению и добровольно вступил в Красную Армию по личному приглашению В. И. Ленина, занимал должности начальника Мобилизационного управления Всероглавштаба (1918—1919), начальника штаба (апрель—июль 1919) и командующего (июль 1919) Восточным фронтом, начальника Полевого штаба Республики и Штаба РККА (1919—1924), одновременно (с марта 1923 до февраля 1924) являлся членом РВС СССР.
Участвовал в разработке и проведении операций по разгрому войск А. В. Колчака, А. И. Деникина и Н. Н. Юденича, считается одним из творцов Орловско-Кромской (Орловско-Курской) операции 1919 года, в ходе которой было остановлено наступление Деникина на Москву. Все время Гражданской войны Лебедев работал в крайне напряженном графике — без выходных, домой приезжал к четырём часам утра.
В 1922—1924 годы по совместительству начальник Военной академии. В 1924—1925 годы состоял для особо важных поручений при РВС СССР. В 1925—1928 годы начальник штаба и помощник командующего войсками Украинского военного округа И. Якира. Входил в состав Всеукраинского центрального исполнительного комитета. Скончался в Харькове.
Приказом РВС СССР от 3 июля 1933 года имя П. П. Лебедева присвоено Киевской артиллерийской школе, которая стала именоваться «Киевская артиллерийская школа имени тов. Лебедева» В Харькове его именем названа улица.