Родился 1 января 1948 года (по сведениям самого Грачёва — 26 декабря 1947) в деревне Рвы Ленинского района Тульской области. В 1964 году окончил школу. С 1965 года года в Советской Армии, поступил в Рязанское высшее воздушно-десантное командное училище, которое окончил с отличием по специальностям «командир взвода воздушно-десантных войск» и «референт-переводчик с немецкого языка» (1969). В 1969-1971 годах служил в должности командира разведывательного взвода отдельной разведроты 7-й гвардейской воздушно-десантной дивизии в Каунасе Литовской ССР. В 1971-1975 годах был командиром взвода (до 1972 г.), командиром роты курсантов Рязанского высшего воздушно-десантного командного училища.

С 1975 года по 1978 год — командир учебного парашютно-десантного батальона 44-й учебной воздушно-десантной дивизии. С 1978 года являлся слушателем Военной академии им. М.В. Фрунзе, которую окончил в1981 г. с отличием и по окончании которой был направлен в Афганистан. С 1981 года принимал участие в военных действиях в Афганистане: до 1982 года — заместитель командира, в 1982-1983 годах — командир 345-го гвардейского отдельного парашютно-десантного полка (в составе Ограниченного контингента советских войск в Афганистане). В 1983 году, по возвращении в СССР, направлен в Псков в качестве начальника штаба — заместителя командира 76-й гвардейской воздушно-десантной дивизии. В 1984 году досрочно присвоено звание полковника. При повторном назначении в ДРА в 1985-1988 годах — командир 103-й гвардейской воздушно-десантной дивизии в составе Ограниченного контингента советских войск.

5 мая 1988 года «за выполнение боевых задач при минимальных людских потерях и за профессиональное командование управляемым соединением и успешные действия 103-й Воздушно-десантной дивизии, в частности, по занятию стратегически важного перевала Сатукандав (провинция Хост) в ходе войсковой операции „Магистраль“», генерал-майору Грачёву было присвоено звания Героя Советского Союза (Медаль «Золотая Звезда» № 11573). После возвращения из Афганистана продолжал службу в воздушно-десантных войсках на различных командных должностях. В 1988-1990 гг. в Академии Генерального штаба Вооружённых Сил СССР.

После окончания был назначен первым заместителем командующего Воздушно-десантными войсками. С 30 декабря 1990 года — командующий Воздушно-десантными войсками СССР (должность генерал-полковника, Грачёв на тот момент — генерал-майор). Всего за время военной службы совершил 647 прыжков с парашютом, часть из них — при испытаниях новой техники. Был 8 раз контужен, получил несколько ранений.

19 августа 1991 года Грачёв выполнил приказ комитета ГКЧП о введении войск в Москву, обеспечил прибытие в город 106-й гвардейской воздушно-десантной дивизии (г. Тула), взявшей под охрану стратегически важные объекты столицы.

23 августа 1991 года указом Президента СССР назначен первым заместителем Министра обороны СССР — Председателем Государственного комитета РСФСР по оборонным вопросам, а 29 октября 1991 года Указом Президента РСФСР Б. Ельцина назначен председателем Государственного комитета РСФСР по оборонным вопросам. По решению Президента СССР повышен в звании до генерал-полковника и назначен первым заместителем министра обороны СССР (август — декабрь1991 г.). С января по март 1992 года — 1-й заместитель главкома Объединёнными Вооружёнными Силами СНГ, являлся сторонником идеи создания системы единых вооружённых сил СНГ.

С 3 апреля 1992 года — первый заместитель министра обороны России, ответственный за осуществление взаимодействия с Главным командованием Объединённых Вооружённых Сил СНГ по вопросам управления воинскими формированиями, находящимися в юрисдикции Российской Федерации.

С 7 мая 1992 года — исполняющий обязанности министра обороны Российской Федерации; в тот же день ему, первому в России после распада СССР, было присвоено звание генерала армии. Стал первым в новейшей истории России военачальником, удостоенным этого звания. С 18 мая 1992 года — министр обороны Российской Федерации.

До 23 июня 1992 года продолжал занимать должность первого заместителя Главнокомандующего Объединенными Вооружёнными Силами СНГ — председателя Государственного комитета Российской Федерации по оборонным вопросам.

В мае 1993 года был введён в состав рабочей комиссии по доработке проекта новой Конституции России.

20 ноября 1993 года Указом Президента назначен членом Совета Безопасности России.

30 ноября 1994 года указом Президента России был включён в Группу руководства действиями по разоружению бандформирований в Чечне.

После ухода с должности Павел Грачёв до осени 1997 года находился в распоряжении Верховного Главнокомандующего.

18 декабря 1997 года согласно специальному указу Президента России приступил к обязанностям советника генерального директора компании «Росвооружение». 27 апреля 1998 года, назначен главным военным советником генерального директора ФГУП «Росвооружение» — «Рособоронэкспорт», официально приступив к исполнению обязанностей.

В апреле 2000 года избран президентом Регионального общественного фонда содействия и помощи ВДВ «ВДВ — боевое братство».

25 апреля 2007 года Грачёв был уволен из группы советников гендиректора «Рособоронэкспорта» «в связи с оргштатными мероприятиями».

С 2007 года — главный советник-руководитель группы советников генерального директора Омского производственного объединения «Радиозавод им. А.С. Попова». В том же году был уволен в запас.

Скончался 23 сентября 2012 года в 3-м Центральном военном клиническом госпитале имени А.А. Вишневского.

Могила Павла Грачёва на Новодевичьем кладбище