Директивой Генерального Штаба ВС РФ от 29 сентября 1994 г. на основе входящего в Московский округ ПВО базировавшегося в Курске 472-го истребительного авиаполка была сформирована 426-я авиационная группа. Местом ее базирования выбрали второй по величине аэропорт Еревана – Эребуни. Уже 28 октября сода прибыл первый транспортный Ил-76 с российскими специалистами. Первым командиром авиагруппы был назначен полковник Раис Валеев, под руководством которого авиаторы начали обустраивать старый гражданский аэропорт и готовить его к эксплуатации боевых самолетов. В начале декабря 1994 г. из Курска в Эребуни перелетело четыре истребителя МиГ-23П и два МиГ-23УБ. Именно в их задачу входило прикрытие от ударов с воздуха частей 102-й российской военной базы на территории Армении. 17 декабря авиагруппа заступила на боевое дежурство. Общая численность персонала базы на тот момент составляла всего 79 человек.
Договор о размещении в Армении российской военной базы сроком на 25 лет был официально подписан 16 марта 1995 г.
В ноябре 1998 г. к авиагруппе добавилась часть обеспечения – 520-я авиационная комендатура. Одновременно с расширением штата было принято решение о перевооружении авиагруппы: на замену выведенным из эксплуатации в ВВС России МиГ-23 должны были поступить истребители четвертого поколения МиГ-29. Оно началось в ноябре 1998 г.
15 декабря 1998 г. на аэродроме Зерноград представители инженерно-авиационной службы 426-й авиагруппы приняли первые пять истребителей МиГ-29 (четыре – типа «9-13» и одну «спарку» МиГ-29УБ). На следующий день самолеты перегнали в Ростов-на-Дону, откуда после прохождения таможенных формальностей они вылетели в Эребуни.
Первая летная смена на МиГ-29 в Эребуни состоялась 24 декабря 1998 г., а уже 12 февраля 1999 г. личный состав авиагруппы заступил на опытно-боевое дежурство в объединенной системе ПВО СНГ в составе пары истребителей.
26 февраля 1999 г. с аэродрома Зерноград в Эребуни забрали вторую группу истребителей, состоявшую из четырех МиГ-29 («9-13») и одного МиГ-29УБ. А в июле и октябре того же года летчики с аэродрома Миллерово перегнали в Армению оставшиеся восемь самолетов. Таким образом, за неполный год 426-я авиационная группа получила в свое распоряжение 18 истребителей МиГ-29. Старые МиГ-23П и МиГ-23УБ, еще несколько месяцев простоявшие на одной стоянке с МиГ-29, были разобраны и утилизированы прямо в аэропорту.
1 июля 2001 г., согласно Директиве Генерального штаба ВС РФ, 426-я авиагруппа и 520-я авиакомендатура были организационно переформированы в 3624-ю авиационную базу.
