Первым делом Валентину Павлову предстояло сформировать состав своего правительства, подобрать себе заместителей и министров. Однако не все министерства ему подчинялись — МИД, МВД и Минобороны входили в кабинет сугубо формально, их истинным начальником был генеральный секретарь, а ныне президент СССР. Павлов отвечал в первую очередь за экономический и социальный блок. Хотя состав министерств и комитетов сократился по сравнению с временами Косыгина почти в два раза, их все равно оставалось около полусотни, и управлять такой махиной без заместителей было бы трудно.
На пост первого заместителя он взял Виталия Хуссейновича Догужиева, который у Рыжкова полтора года работал простым замом. Догужиев родился в 1935 году, в молодом возрасте стал директором уральского завода в сфере Минобщемаша. Затем он руководил более крупным заводом там же, на Урале, а в 1983-м при новом министре Олеге Бакланове был переведен в Москву его заместителем. В 1988–1989 годах — после избрания Бакланова секретарем ЦК — Догужиев работал министром общего машиностроения, а с лета 1989-го стал заместителем председателя Совмина. К августу 1991-го у Павлова было уже три первых заместителя, но именно Догужиев стал исполняющим обязанности, когда премьер попал в больницу. Он отвечал за чрезвычайные ситуации, вообще оперативное управление. Догужиев считался сильным руководителем, имел опыт не только министерской работы в Москве, но и управления большими и сложными предприятиями.
Вторым первым замом был приглашен Владимир Макарович Величко, до того министр тяжелого машиностроения. Он родился в 1937 году и в возрасте тридцати четырех лет стал директором завода «Большевик» (прежде Обуховский завод). Предприятие подчинялось Министерству оборонной промышленности и производило среди прочего командные пункты для РВСН. Ему еще не было сорока, когда его перевели в Москву и назначили первым заместителем новообразованного Министерства энергетического машиностроения, которое занималось производством турбин и котлов. Министром он стал в 1983-м, а при Рыжкове его министерство вновь объединили с Минтяжпромом (из которого его выделили в 1975-м).
Наиболее интересным было назначение уже в мае 1991 года третьего первого заместителя (и одновременно министром экономики и прогнозирования) — Владимира Ивановича Щербакова, которому исполнился только 41 год. Он был наиболее перспективным и необычным представителем нового поколения. За его плечами была комсомольская работа в Тольятти в то время, когда там строился ВАЗ, на котором он вскоре возглавил Планово-экономическое управление, а затем, в 33 года, перешел заместителем директора по экономике на КамАЗ — по советским меркам в неприлично молодом возрасте для такого огромного предприятия. С 1985 года Щербаков работал в Москве начальником отдела в Госкомитете по труду и социальным вопросам, который возглавил в 1989-м. Он был восходящей звездой и дышал Павлову в затылок. Горбачев рассматривал его как следующего премьера. Но пребывание Щербакова в правительстве оказалось краткосрочным. После 1991 года он ушел в бизнес и стал удачливым предпринимателем, открыв дело по сборке автомобилей. Павлов знал о планах Горбачева заменить его на Щербакова, но «держал удар», не подавая виду, и не позволял возможным опасениям отравлять работу кабинета.
«Простыми замами» у Павлова стали Юрий Маслюков, отвечавший за оборонку, академик Николай Лаверов по науке, «атомщик» Лев Рябев, ведший Топливно-энергетический комплекс (ТЭК), Герой Соцтруда Федор Сенько по АПК, Биходжал Рахимова из Таджикистана, курировавшая социалку. Бывший помощник Косыгина — Игорь Простяков стал управляющим делами кабинета. Немало министров Павлов менял по ходу работы. Были у него и неожиданные назначения — Леонид Матюхин возглавил Министерство путей сообщения с поста начальника Горьковской железной дороги, Саламбек Хаджиев, чеченец, бывший директор НИИ в Грозном, стал министром химической и нефтеперерабатывающей промышленности, эстонец Валерий Паульман стал министром по труду и социальным вопросам.
Структура Кабинета министров была еще во многом советской — оставалось много отраслевых министерств, однако одномоментно отказаться от «ручного» управления отраслями и пустить все на самотек было невозможно ввиду очевидных социальных и экономических последствий. Тем не менее при Валентине Павлове продолжались преобразования — так, например, Министерство лесной промышленности перестало существовать с 1 апреля, преобразовавшись в государственную корпорацию по производству лесобумажной продукции «Российские лесопромышленники», Министерство тяжелого машиностроения в концерн «Тяжэнергомаш».