Биография
Родился в деревне Кайлык, ныне Уярского района Красноярского края, в семье крестьянина.
Начало военной службы
С 1926 года — в Красной Армии. В 1929 году П. Н. Кулешов окончил Томское артиллерийское училище и был направлен для прохождения службы в Нижний Новгород на должность командира огневого взвода батареи 50-го стрелкового полка. Затем он командовал учебным взводом в полковой школе, формировал отдельный резервный артиллерийский дивизион в Новосибирске, был командиром учебной батареи Томского артиллерийского училища.
В 1933 году направлен на учёбу на инженерно-командный факультет Военную академию имени Ф. Э. Дзержинского. После окончания академии служил в Главном артиллерийском управлении Наркомата обороны СССР на должности инспектора по военно-учебным заведениям. В 1939 году поступил в Военную академию Генерального штаба, которую успешно окончил в сентябре 1941 года.
Великая Отечественная война
После окончания академии П. Н. Кулешов один месяц был помощником начальника отдела в Генеральном штабе, где занимался планированием обеспечения действующей армии боеприпасами. В октябре 1941 года П. Н. Кулешов получил приказ срочно формировать в посёлке Алабино Московской области 3-й гвардейский минометный полк — полк «катюш». 3-й полк ГМЧ (гвардейских минометных частей) стал учебной базой по подготовке командных кадров для оперативных групп ГМЧ на фронтах. В том же октябре 1941 года П. Н. Кулешов назначен командиром оперативной группы ГМЧ на Северо-Западном фронте, вскоре стал командиром такой же группы на Волховском фронте. Эта группа под его командованием сыграла значительную роль в успешном исходе боёв в районе Тихвина, когда советские войска остановили противника и не позволили ему выйти к Ладожскому озеру с целью захвата единственного пути сообщения между Большой землей с осажденным Ленинградом.
На Волховском фронте П. Н. Кулешов был ранен. После лечения во фронтовом госпитале, Павел Николаевич продолжал командовать Волховской оперативной группой и принимал активное участие в прорыве блокады Ленинграда в январе 1943 года. В июне 1943 года он был отозван с фронта и назначен заместителем командующего гвардейскими минометными частями Красной Армии. В этой должности часто привлекался к работе в оперативных группах представителей Ставки Верховного Главнокомандования. Выезжал на Северо-Кавказский, Воронежский, 4-й Украинский и 2-й Украинский фронты для организации усиления ударных группировок гвардейскими минометными частями, организации правильного использования реактивной артиллерии и их своевременного обеспечения боеприпасами.
В конце 1943 года на фронтах были введены должности заместителей командующего артиллерией фронта по гвардейским минометным. Генерал-майор артиллерии Кулешов тогда же был назначен на данную должность на 1-м Прибалтийском фронте. Участвовал в ряде наступательных операций, особенно успешно проявил себя в Белорусской стратегической наступательной операции летом 1944 года.
В августе 1944 года П. Н. Кулешов вторично отозван с фронта и назначен с повышением на должность заместителя начальника штаба артиллерии Красной Армии, где занимался вопросами формирования новых частей реактивной артиллерии для фронтов, обеспечения ГМЧ боеприпасами и техникой, планирования боевых действий артиллерии и ГМЧ при разработке стратегических операций в Генеральном штабе, контролем производства артиллерийской техники. Генерал-лейтенант артиллерии (ноябрь 1944 г.).