В 18 лет он вступил в Красную Армию, а в 1929 году Павел Кулешов оканчивает Томское артиллерийское училище , после которого направляется для прохождения службы в Нижний Новгород на должность командира огневого взвода батареи 50-го стрелкового полка.

В 1933 году он направляется на учёбу на инженерно-командный факультет Военной академии имени Ф. Э. Дзержинского, а в 1939 году поступает в Военную академию Генерального штаба, которую успешно окончивает в сентябре 1941 года.

В октябре 1941 года П. Н. Кулешов получил приказ срочно формировать в посёлке Алабино Московской области 3-й гвардейский минометный полк — полк «катюш». В дальнейшем за годы войны он проявил себя как отличный боевой командир и выдающийся военноначальник, завершив Великую Отечественную войну в звании генерал-лейтенанта артиллерии.

После войны П. Н. Кулешов трудился в Академии имени Ф. Э. Дзержинского, привлекался к разработкам новых ракетно-артиллерийских вооружений, работал на испытательном полигоне в Астраханской области, работал в Центральном аппарате Министерства обороны СССР, был заместителем Главнокомандующего Войсками противовоздушной обороны страны. Став генерал-полковником П. Н. Кулешов , занимался поставками ракетной техники в дружественные страны Ближнего Востока и на Кубу, содействовал им в освоении этой боевой техники.

С 1965 года П. Н. Кулешов — начальник Главного ракетно-артиллерийского управления Министерства обороны СССР. А в 1967 году ему было присвоено маршал артиллерии.

До последних дней жизни работал на должности специалиста в ГРАУ.