В 30-х годах прошлого столетия в СССР начинается активное строительство аэропортов местных и союзных авиалиний. В Приморском крае к освоению первых полевых аэродромов и воздушного пространства приступают в 1931 году. Летом 1932 года начаты первые одиночные коммерческие полеты. Идет строительство гидроаэропорта на Второй речке (Владивосток) и аэропорта «Озерные Ключи» (Артем). 27 августа 1932 г. гидросамолет выполнил первый технический рейс, а 2-го сентября этого года он доставил из Хабаровска на Вторую Речку первых четырех пассажиров. С этого дня начинается отсчет истории Владивостокского авиапредприятия.

C тех пор пассажирские полеты между Владивостоком и Хабаровском стали регулярными. В 1934 году аэропорт на Второй речке был перенесен на сушу, а на его базе создано звено самолетов У-2,  откуда начали выполняться регулярные полеты, были открыты аэропорты «Иман» и «Озерные Ключи», создана санитарная авиация, осваивались новые для того времени типы самолетов и виды работ.

В военные годы По-2 взяли на себя перевозки свинцово-оловянного концентрата для нужд фронта, а в конце войны — перевозку снарядов. В июле 1941 года авиазвено самолетов У-2,  П-5 и Ш-2 перебазируется в аэропорт «Озерные Ключи», открыв тем самым новую эпоху в истории развития гражданской авиации Приморья.

В послевоенное десятилетие самолеты По-2 и Ш-2 нашли широкое применение на авиационно-химических работах и прибрежной разведке рыбы, в обслуживании геологов и патрулировании лесов. Развивалась сеть посадочных площадок Приморского края, послужившая фундаментом строительства аэропортов местных линий в 60-е и 80-е годы. Пассажирские рейсы по линии Москва — Владивосток с 1948 года выполняются на самолете Ил-12.

С 1953 года самолет Ан-2 стал своеобразной школой мастерства для пилотов, на нем освоили многие виды работ и перевезли тысячи пассажиров. Приняв трудовую вахту от По-2 , «Аннушка» стала незаменимой по обработке сельхозугодий. В эти же годы авиаторы Приморья начали осваивать и вертолеты. Первенец - Ми-4 надежно трудился в авиапредприятии около 30 лет, затем были: Ми-1,  Ка-15,  Ми-8,  Ми-2,  Ка-26,  Ка-32,  Ми-171.

В 1956 году самолет Ту-104 открыл эру реактивной авиации. В мае 1958 года выполнен первый пробный беспосадочный полет на самолете Ту-114Д из Москвы во Владивосток, а в августе Владивостокское авиапредприятие приступает к базовой эксплуатации самолета Ли-2 , который в течение 15 последующих лет совершал регулярные полеты с пассажирами из аэропорта «Озерные Ключи» в Хабаровск.

К этому времени аэродром «Озерные Ключи» исчерпал свои возможности по приему большого количества тяжелых самолетов. С 1959 по 1964 гг. был возведен комплекс необходимых наземных сооружений, позволивших начать регулярные полеты самолетов Ту-104 (1958 г.), ИЛ-18 (1963 г.), Ан-10 (1964 г.), резко увеличить объемы пассажирских перевозок. В феврале 1961 года построено первое кирпичное здание аэровокзала с пропускной способностью 200 человек. Это было начало большого аэропорта «Владивосток».

В 60–80 годах пилоты Владивостокского авиаотряда были первопроходцами в обслуживании рыбодобывающих флотилий и ледоколов. 30 августа 1961 года приморские авиаторы впервые на Дальнем Востоке начали обслуживание промышленности с помощью вертолетов Ми-1.  Вертолеты Владивостокского авиапредприятия были и летающими кранами и скорой помощью.

Появление в 70-х реактивного мини-лайнера Як-40 и вертолета Ми-8 способствовало оживлению перевозок и обслуживанию нужд народного хозяйства. В 1973 году авиапредприятие приступило к строительству нового аэровокзала, который был сдан в эксплуатацию в конце 1976. Аэропорт «Владивосток» начал регулярный прием Ту-154. Одновременно шло динамичное развитие структурных комплексов авиапредприятия - создавались новые эскадрильи Як-40 и Ми-8.  Завершение строительства ВПП-2 в июне 1985 года позволило принимать все типы современных самолетов и осуществлять прямое воздушное сообщение между Владивостоком и Москвой на самолете Ил-62.

В 1990 году, заключив первый международный контракт в Папуа — Новой Гвинее на использование вертолетов Ка-32,  Владивостокский объединенный авиаотряд выходит на международный рынок. Аэропорт «Владивосток» с 1992 года становится международным. В этом же году предприятие приобретает в собственность два самолета Ил-76,  начинается базовая эксплуатация самолетов Ил-76 и Ту-154.

С января 1994 года мы представляем собой Открытое Акционерное Общество «Владивосток Авиа», включающее в себя авиакомпанию и аэропорт. В 1995 году приобретен первый магистральный пассажирский самолет Ту-154 М в собственность.

В течение 1997–1999 годов авиапарк «Владивосток Авиа» увеличился еще на несколько ВС Ту-154.

4 марта 1999 года сдан в эксплуатацию международный терминал аэропорта «Владивосток».

В 2001 году, в январе и мае, в авиапарк компании поступили два среднемагистральных самолета Ту-154 М.

2002 год ознаменовался для «Владивосток Авиа» приобретением очередного воздушного судна Ту-154 М и сдачей первой очереди строительства инженерно-лабораторного корпуса авиакомпании.

В течение 2003–2004 годов компания приобрела еще шесть ВС Ту-154 М.

В 2005 году авиакомпания «Владивосток Авиа» первая в России и мире приступила к эксплуатации новейших дальнемагистральных самолетов Ту-204-300. Также, в этом году компания сдала вторую очередь инженерно-лабораторного корпуса. Торжественной церемонией открытия в декабре 2006 года в аэропорту «Владивосток» завершилась масштабная реконструкция аэровокзала внутренних авиалиний.

5 февраля 2007 года в транспортном парке компании «Владивосток Авиа» появился первый на Дальнем Востоке самолет зарубежного производства — среднемагистральный Аirbus A320.

25 января 2008 года в авиакомпании «Владивосток Авиа» состоялась торжественная встреча двух самолетов Airbus А320 в фирменной раскраске компании, а 30 июля поступило еще одно воздушное судно. Таким образом, в авиапарке «Владивосток Авиа» стало четыре самолета этого типа. С приобретением двух самолетов Ту-204-300 парк этих машин во «Владивосток Авиа» увеличен до 6 единиц.

15 февраля 2008 года ОАО «Владивосток Авиа» завершило реорганизацию в форме выделения ОАО «Международный аэропорт Владивосток» (МАВ). Соответствующая запись была внесена в этот день в Единый государственный реестр юридических лиц. Таким образом, в Приморском крае из некогда единого авиационного предприятия сформировалось два: авиакомпания — ОАО «Владивосток Авиа» и аэропорт — ОАО «МАВ».

2009 год отмечен дальнейшим развитием «Владивосток Авиа». В рамках своего расписания в этом году авиакомпания открыла прямые регулярные рейсы из большинства дальневосточных городов в Москву, Санкт-Петербург, Сочи. Ежедневно «Владивосток Авиа» выполняет из трех базовых аэропортов: Владивостока, Хабаровска, Москвы десятки российских и международных рейсов.

Авиакомпания «Владивосток Авиа» первой в России приступила к эксплуатации широкофюзеляжных дальнемагистральных воздушных судов типа А330-300, вместимостью 327 пассажирских кресел. В течение года был приобретен и пятый A320.

9 декабря 2009 года авиакомпания перевезла своего первого миллионного пассажира.