Павел Шестаков родился и большую часть жизни прожил в г.  Ростове-на-Дону.

В связи с Великой Отечественной войной и эвакуацией учился во многих школах. В 1954 году окончил историко-филологический факультет Ростовского Государственного Университета. Работал школьным учителем в Первомайске (Украина), затем вернулся в Ростов, был сотрудником Ростовского областного музея краеведения, литературным редактором в Ростовском книжном издательстве и журнале «Дон». Двенадцать лет с 1970 по 1982 год был собственным корреспондентом«Литературной газеты» по Ростовской области.

В 1966 году в журнале «Урал» (Свердловск) была опубликована его первая повесть «Через лабиринт» в детективном жанре. Журнал «Урал» занял особое место в писательской судьбе Шестакова. Большинство его произведений впервые были напечатаны в этом журнале. Повесть «Через лабиринт» привлекла внимание неординарностью сюжета и образом центрального героя — инспектора Игоря Николаевича Мазина. По его имени последующие произведения П. Шестакова составили своего рода «мазинский цикл». Это «Страх высоты», «Игра против всех», «Давняя история», «Рапорт инспектора», «Остановка», «Клад», «Вертеп» и другие.

В 1971 году П. Шестаков был принят в Союз писателей СССР (с 1991 года — член Союза российских писателей).