В апреле 1972 г. заводская отработка закончилась и начался этап государственных совместных испытаний.
Для ускорения проведения лётно- морских испытаний Як-36М Главный штаб ВМФ выделил ПКР "Москва". В центре его вертолетной палубы смонтировали взлётно посадочную площадку (ВППл) размером 20x20 м, изготовленную из стальных листов толщиной 10-мм, покрытых термостойкими плитами. 16 ноября 1972 г. "доработанный" корабль прибыл в район Феодосийского залива.
С тем, чтобы дать представление лётчику-испытателю М. С. Дексбаху о методике захода для посадки на корабль, ему дали несколько ознакомительных полётов на вертолёте Ка-25 с инструктором – лётчиком- инспектором боевой подготовки авиации ЧФ подполковником Н.П. Праховым. Расстояния, которые корабельные РЛС измеряли в милях и кабельтовых, предварительно перевели в метрические, и информацию экипаж вертолёта получал в километрах и метрах. Кроме того, по оси захода, в точках, соответствующих удалению запуска ПД и переводу сопел ПМД в вертикаль, выставили корабли.
Утром 18 ноября 1972 г. самолёт Як-36М, пилотируемый лётчиком-испытателем М. С. Дексбахом, взлетел с аэродрома Кировское, вышел в район стоянки корабля и стал заходить на посадку с кормы. На удалении от корабля 6,5-8,5 км был произведён запуск ПД. Через некоторое время, подняв столб брызг, самолёт произвел посадку. 22 ноября 1972 г. М.С. Дексбах выполнил полёт по "полному профилю" с палубы корабля, после чего самолёт произвёл посадку на аэродроме. В последующих полётах на ПКР "Москва" оценивалась возможность эксплуатации самолёта при качке, которую имитировали, ввиду отсутствия подходящих условий на Чёрном море, с помощью корабельных успокоителей качки. После окончания полётов площадку за ненадобностью демонтировали.
Первый этап государственных совместных испытаний продолжался до сентября 1974 г. Самолеты Як-36М после соответствующих формальностей допустили к эксплуатации в строевых частях и для проведения государственных испытаний головного тяжёлого авианесущего крейсера (ТАКР) пр. 1143 "Киев".
Решение о запуске Як-36М в серийное производство (18 боевых самолётов и два учебных самолёта за три года) на Саратовском авиазаводе было принято в 1973 г., и уже в следующем году там собрали первые три серийные машины. На этом предприятии (до войны он назывался Саратовский завод комбайнов и выпускал самолёты Як-1) строились фюзеляжи трех опытных машин, а также (по договору с Черноморским судостроительным заводом) габаритно-массовый макет самолёта для отработки его размещения на ангарной палубе строящегося "Киева".