В США тактико-технические требования к такой ракете были сформированы уже в 1976 г, а в 1981 г. фирма «Хьюз», выиграв конкурс, получила контракт на окончательную разработку УР AIM-120 AMRAAM. Она должна была поражать воздушные цели на дальности до 65 км под любым ракурсом и в любых метеоусловиях. Предусматривалась замена ракет «Спэрроу» и «Скай Флэш» (английский аналог «Спэрроу») ракетами AMRAAM на самолетах F-14, F-15, F-16, F- 18, «Торнадо» и вооружение новыми боеприпасами всех вновь создаваемых самолетов. Ракета имела комбинированную систему наведения: инерциальное наведение с радиокоррекцией на начальном этапе и активное радиолокационное самонаведение на конечном участке полета. Такая система наведения обеспечивала полет по траектории без чрезмерных перегрузок при следовании за маневрирующей целью, и, что самое главное, позволяла почти одновременно пускать с самолета до восьми ракет по разным целям.
В 1982 г. разработка подобной ракеты, получившей в прессе наименование РВВ-АЕ (а впоследствии Р-77), началась и в Советском Союзе на Гос. МКБ «Вымпел». Создававшаяся с некоторым опозданием по сравнению с AMRAAM, новая отечественная УР имела перед «американкой» довольно существенные преимущества: обладала большей дальностью пуска (до 90 км), лучшими возможностями по поражению маневрирующих и низколетящих целей, складывающиеся рули позволяли осуществлять ее внутрифюзеляжное размещение в перспективных самолетах с пониженной радиолокационной заметностью. Серийное производство AMRAAM началось в 1986г., а спустя три года началась подготовка к серийному производству Р-77 на Украине, в то время безусловно входившей в СССР.
Ориентируясь на перспективные средства поражения, ВВС еще в начале 80-х гг. сформулировали требования к модернизации только недавно принятых на вооружение самолетов МиГ-29, МиГ- 31 и Су-27. Кроме того, стремясь увеличить эффективность авиации за счет привлечения истребителей для нанесения ударов по наземным и подводным целям (по примеру американских F-14D, F- 15С/Е, F-16C и F-18C адаптированных для подобных задач), ВВС задали для самолетов МиГ-29М и Су-27М большую номенклатуру авиационных управляемых боеприпасов класса «воздух-поверхность». Расширение боевых задач потребовало введения новых режимов работы прицельных систем, что повлекло необходимость создания РЛС с совершенно иными принципами работы и другой внутренней структурой. Большие конструктивные затруднения, возникшие при создании таких РЛС, стали одним из камней преткновения, на котором споткнулись создатели этих самолетов.
Работа над созданием МиГ-31 М началась в 1983 г., когда вышло совместное Постановление ЦК КПСС и СМ СССР, в котором ОКБ им. А.И.Микояна поручалось создание авиационного комплекса перехвата, оснащенного разрабатываемыми МКБ «Вымпел» ракетами большой дальности Р-37 и ракетами средней дальности Р-77. Кроме наращивания огневой мощи самолеты МиГ-31 М предполагалось оснастить новым поколением БРЭО, позволяющем их экипажам обеспечивать ведение групповых боевых действий, выдавая целеуказание самолетам МиГ-23, МиГ-29, Су-27 и МиГ-31, то есть использоваться в качестве мини-АВАКСов.
Внешне перехватчик изменился незначительно: более внушительно стала выглядеть носовая часть, где стоял новый локатор, наплывы на передней части крыла несколько увеличились и приобрели оживальную форму, гаргрот за кабиной пилотов стал более внушительным, на концах крыла разместились контейнеры для станций активных помех. Самолет получил также штатную систему дозаправки топливом в воздухе и модернизированные двигатели, развивающие несколько большую тягу, что было необходимым в связи с возросшей взлетной массой.