Первые экспериментальные пуски УР Р-33 по ПКР летчики 865-го иап успешно выполнили еще в 1991 г., но эксперимент — есть эксперимент. С конца 1990-х гг. практические пуски ракетами Р-33 по ПКР разных типов выполнялись регулярно. В числе первых ПКР поразили экипажи в составе лётчиков: подполковников П.А. Войтова, В.А. Корягина, А.В. Конистяпина, Н.А. Мищенко, майоров И.А. Корсуна, И.А. Годуна; штурманов: подполковника СВ. Маслова, майоров В.Н. Романова, В.Б. Егорова, С.Л. Мариакрия, В.М. Лагуна.

Практическим пускам предшествовали «внутриполковые» учения. Как правило, в них принимали участие четыре МиГа. Один перехватчик имитировал высотную ракету, второй — маловысотную, два других истребителя перехватывали «цели».

Возвращаясь в более ранние времена стоит вспомнить о том, что в литературе немало написано про то, как появление МиГ-31 на Дальнем Востоке привело к снижению активности американской авиации у границ СССР. Не совсем так. Количество подъемов дежурных сил снижения активности вероятного противника после 1984 г. не подтверждают, наоборот — активность увеличилась. А вот наглость снизилась! Причины снижения агрессивности очевидны: качественно иной уровень МиГ-31 в сравнении с Су-15 и МиГ-23.

По итогам боевой подготовки, проведения учений с выполнением боевых стрельб в 2001, 2002, 2003 и 2007 гг. полк завоевывал Приз Главнокомандующего Военно-Морским Флотом среди авиационных эскадрилий истребительной авиации. Неоднократно полк признавался лучшим в группировке Войск и Сил на северо-востоке Российской Федерации и на Тихоокеанском Флоте. В 2001 г. возобновилась подготовка лётного состава, ранее не летавшего на МиГ-31. В 2005—2007 гг., после длительного перерыва в полётах, вводятся в строй лётчики, не выполнявшие полёты в течение целого ряда лет по причинам, от них не зависящим: майоры Е.В. Мелехов, А.А. Аносов., В.Н. Литвин, СР. Петренко, А.И. Сыпачев, А.А. Лагунин, А.Б. Сармин, С.Н. Овчинников, капитан А.В. Казаков.

С начала эксплуатации в полку самолёта МиГ-31, молодые лётчики после окончания военных училищ, для прохождения службы в полк не направлялись ввиду сложности пилотирования самолёта МиГ-31 и особого места дислокации части (полёты проходят над акваториями Тихого океана, Охотского моря, гористой и малоориентирной местностью). В полк, в основном, прибывали лётчики уже с квалификацией не ниже 2-го класса из других частей. Однако в 2003 г. полк пополнился молодыми лётчиками-выпускниками лётных училищ. До начала полетов на МиГ-31 планировалось довести пополнение на L-39 в Центре подготовки лётного состава авиации ВМФ в г. Остров Псковской области до уровня 2-го класса. Процесс, что называется, пошел, но быстро застопорился из-за отсутствия запасных частей и изношенности «Элок». В 2006 г. подготовку летчиков МиГ-31 в Центре прекратили. Теоретическое обучение молодежь прошла в Центре авиации и ПВО в Саваслейке, а практически освоила МиГ-31 в 2007-2009 гг. непосредственно в Елизове.

В марте 2007 г. полк подвергся проверке Военной Инспекцией Министерства Обороны РФ.

Полку была поставлена задача на перебазирование восьмью экипажами МиГ-31 с оружием на борту на аэродром Домна под Читой с выполнением боевых стрельб на государственном полигоне Телемба. К перегону и выполнению стрельб привлекались подполковники П.А. Войтов, К.О. Волошин, СВ. Маслов, А.Г. Маркин, А.Р. Булдаков, Н.А. Мищенко, майоры И.А. Корсун, С.Г. Кодерле, Е.О. Еремин, В.Н. Романов, С.П. Мариакрий, В.Б. Егоров, В.М. Лагун, Ю.Б. Молчанов, А.Е. Бекетов, капитан С.Г. Мурга. В ходе проведения инспекции впервые строевой авиационной частью были успешно уничтожены с первой атаки две высотные скоростные мишени типа «Стриж». Мишени сбили экипажи в составе подполковника А.Г. Марикна и майора В.Н. Романова, майора И.А. Корсуна и майора В.М. Лагуна; наведение истребителей на цель осуществлял майор В.И. Лянгасов. По результатам инспекции ВИМО полк получил оценку «хорошо».