За время разработки УР К-80 изменилась тактика действий авиации вероятного противника, которая перешла к прорыву к цели на малых высотах. Исходя из этого Постановлением от 26 декабря 1968 г  1044-381 была задана разработка модернизированного варианта комплекса Ту-128-80, которая и была осуществлена к началу семидесятых годов. Испытания во Владимировке проходили с 10 марта 1973 г. по 24 июля 1974 г. Приказом Министра обороны  00104 от 10 июня 1979 г модернизированный комплекс Ту-128-80М с ракетой К-80М был принят на вооружение.

С учетом уточненных требований "изделия 36М" - ракеты Р-4МР и Р-4МТ комплектовалась новой "радийной" ГСН ПАРГ-15ВВ, усовершенствованной тепловой Т-80НМД, неконтактным оптическим взрывателем "Сокол", доработанным двигателем ПРД-84М. Была повышена помехоустойчивость, уменьшена нижняя граница диапазона высот применения. Цели поражались на высотах от 50 м при пусках вдогон цели и от 2 км при атаке в переднюю полусферу, которая по-прежнему могла осуществляться с использованием только "радийных" ракет.

В зарубежной прессе приводится также информация о разработке варианта ракеты с пассивной радиолокационной ГСН, предназначенной для поражения самолетов типа АВАКС и постановщиков помех на дальностях до 40 км.

Помимо прямой линии непосредственной модернизации самолета Ту-128 и ракет Р-4 в шестидесятые годы активно велись проектные работы по более радикальному совершенствованию тяжелого перехватчика и его вооружения.