Родился 3 (16) августа 1914 года в селе Малая Кирсановка (ныне село Малокирсановка Матвеево-Курганского района Ростовской области). В 1930 году окончил 7 классов в селе Фёдоровка (ныне Неклиновского района Ростовской области). С 1930 года жил в городе Таганроге (ныне Ростовской области). В 1933 году окончил школу фабрично-заводского ученичества (ФЗУ) трамвайщиков. В 1933-1934 гг. работал слесарем на авиационном заводе № 31 в Таганроге. В 1935 году окончил рабфак при Таганрогском индустриальном институте. С июля 1935 года в рядах Красной Армии. По комсомольской путёвке направлен в Сталинградское военное авиационное училище лётчиков, которое окончил в ноябре 1938 года. Служил командиром звена 7-го ИАП (в Ленинградском военном округе). Летал на И-15бис.

Участник Советско-Финляндской войны с 30 ноября 1939 по 13 марта 1940 гг. в должности командира звена 2-й эскадрильи 7-го ИАП (в декабре эскадрилья временно была передана в подчинение 68-го ИАП). Летал на И-15бис и И-153. Совершил 131 боевой вылет. Воздушных побед не имел. 25 декабря 1939 года был подбит огнём своего же истребителя И-16 (лётчик 26-го ИАП лейтенант А. Н. Сторожаков, будущий Герой Советского Союза, перепутал И-15бис с финским "Бульдогом"). П. С. Кутахов сумел довести подбитую машину до своей территории, где совершил вынужденную посадку. Самолёт при этом был разбит. В январе 1940 года был сбит зенитным огнём, спасся на парашюте.

Затем продолжал службу командиром звена и заместителем командира эскадрильи 7-го ИАП (в Ленинградском военном округе). Летал на И-153, в июне 1941 года переучился на новый МиГ-3.

С 22 июня 1941 года на фронтах Великой Отечественной войны в должности заместителя командира эскадрильи 7-го ИАП (5-я САД, ВВС Северного фронта), летал на МиГ-3. С июля 1941 года воевал в составе 145-го ИАП (4 апреля 1942 года преобразован в 19-й Гвардейский ИАП). 28 января 1942 года - командир эскадрильи. Летал на И-16, МиГ-3, ЛаГГ-3 и "Аэрокобре". Сражался на Северном и Карельском фронтах. Участвовал в обороне Ленинграда, Мурманска и Заполярья, прикрытии союзнических конвоев.

К 17 февраля 1943 года командир 1-й эскадрильи 19-го Гвардейского истребительного авиационного полка (258-я истребительная авиационная дивизия, 7-я Воздушная армия, Карельский фронт) Гвардии майор П. С. Кутахов совершил 262 боевых вылета, в 40 воздушных боях лично сбил 6 и в группе 15 самолётов противника (в наградном листе говорится о 7 личных и 24 групповых победах). За эти подвиги был представлен к высшей награде страны.

27 марта 1943 года был сбит в воздушном бою, спасся на парашюте. С апреля 1943 года - помощник командира полка по воздушно-стрелковой службе. Указом Президиума Верховного Совета СССР от 1 мая 1943 года удостоен звания Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда" (№ 1026). С 7 мая 1944 года командовал 20-м Гвардейским ИАП (1-я Гвардейская смешанная авиационная дивизия), где продолжал летать на "Аэрокобре". Сражался на Карельском фронте и в составе ВВС 14-й Отдельной армии. Участвовал в Свирско-Петрозаводской и Петсамо-Киркенесской операциях.

К январю 1945 года командир 20-го Гвардейского истребительного авиационного полка (16-я Гвардейская истребительная авиационная дивизия, 7-я Воздушная армия, Карельский фронт) Гвардии подполковник П. С. Кутахов совершил 367 боевых вылетов, провёл 79 воздушных боёв, в которых сбил лично 12 и в составе группы не менее 15 самолётов противника (вероятно имел и больше групповых побед).

После окончания войны до ноября 1948 года продолжал командовать 20-м Гвардейским ИАП (в Беломорском военном округе; город Петрозаводск, Карелия). Летал на Як-1, Як-9 и Як-3. В 1949 году окончил Высшие офицерские лётно-тактические курсы ВВС (в Липецке). С октября 1949 года - заместитель командира 175-й ИАД (ГСВ в Германии). С декабря 1950 года - командир 145-й ИАД (ГСВ в Германии), летал на МиГ-15 и МиГ-17. С ноября 1951 года - заместитель командира, а с декабря 1953 года - командир 71-го ИАК (ГСВ в Германии), летал на МиГ-15бис. В 1957 году окончил Высшую военную академию (Военную академию Генерального штаба). С декабря 1957 года - заместитель командующего по боевой подготовке, а с октября 1959 года - 1-й заместитель командующего 30-й Воздушной армией (в Прибалтийском военном округе), летал на МиГ-17 и МиГ-21. С августа 1961 года - командующий 48-й Воздушной армией (в Одесском военном округе), летал на МиГ-21Ф и Су-7Б. С июля 1967 года - 1-й заместитель Главнокомандующего ВВС. С марта 1969 года - Главнокомандующий ВВС и заместитель министра обороны СССР. Указом Президиума Верховного Совета СССР от 15 августа 1984 года Главный маршал авиации П. С. Кутахов награждён орденом Ленина и второй медалью "Золотая Звезда". Умер 3 декабря 1984 года. Похоронен в Москве, на Новодевичьем кладбище.

Бронзовый бюст П. С. Кутахова установлен в селе Малокирсановка (Матвеево-Курганский район Ростовской области). В Москве на доме, в котором он жил, и в Таганроге на здании школы, в которой он учился, установлены мемориальные доски. Бюст установлен также в городе Люберцы (Московская область). Его именем названы улицы в посёлке Мурмаши (Кольский район Мурманской области) и селе Малокирсановка, а также гимназия № 41 в городе Люберцы. С 1989 года имя героя носит рыболовный траулер "Павел Кутахов" (порт приписки - Мурманск). В 1985-1998 гг. имя П. С. Кутахова носило Армавирское высшее военное авиационное училище лётчиков.

Награждён орденами: Ленина (01.05.1943, 15.08.1974, 21.02.1978, 15.08.1984), Октябрьской Революции (04.05.1972), Красного Знамени (01.05.1942, 13.07.1942, 22.02.1955, 30.12.1956, 22.02.1968), Кутузова 1-й степени (04.11.1981), Александра Невского (05.11.1944), Отечественной войны 1-й степени (22.09.1943), Красной Звезды (15.11.1950, 29.04.1954), "За службу Родине в Вооружённых Силах СССР" 3-й степени (17.02.1976); медалями, в том числе "За боевые заслуги" (06.11.1945); иностранными наградами.