В 30-х годах прошлого столетия в СССР начинается активное строительство аэропортов местных и союзных авиалиний. В Приморском крае к освоению первых полевых аэродромов и воздушного пространства приступают в 1931 году. Летом 1932 года начаты первые одиночные коммерческие полеты. Идет строительство гидроаэропорта на Второй речке (Владивосток) и аэропорта «Озерные Ключи» (Артем). 27 августа 1932 г. гидросамолет выполнил первый технический рейс, а 2-го сентября этого года он доставил из Хабаровска на Вторую Речку первых четырех пассажиров. С этого дня начинается отсчет истории Владивостокского авиапредприятия.
C тех пор пассажирские полеты между Владивостоком и Хабаровском стали регулярными. В 1934 году аэропорт на Второй речке был перенесен на сушу, а на его базе создано звено самолетов У-2, откуда начали выполняться регулярные полеты, были открыты аэропорты «Иман» и «Озерные Ключи», создана санитарная авиация, осваивались новые для того времени типы самолетов и виды работ. В военные годы По-2 взяли на себя перевозки свинцово-оловянного концентрата для нужд фронта, а в конце войны — перевозку снарядов. В июле 1941 года авиазвено самолетов У-2, П-5 и Ш-2 перебазируется в аэропорт «Озерные Ключи», открыв тем самым новую эпоху в истории развития гражданской авиации Приморья.
В послевоенное десятилетие самолеты По-2 и Ш-2 нашли широкое применение на авиационно-химических работах и прибрежной разведке рыбы, в обслуживании геологов и патрулировании лесов. Развивалась сеть посадочных площадок Приморского края, послужившая фундаментом строительства аэропортов местных линий в 60-е и 80-е годы. Пассажирские рейсы по линии Москва — Владивосток с 1948 года выполняются на самолете Ил-12. В 1956 году самолет Ту-104 открыл эру реактивной авиации. В мае 1958 года выполнен первый пробный беспосадочный полет на самолете Ту-114Д из Москвы во Владивосток, а в августе Владивостокское авиапредприятие приступает к базовой эксплуатации самолета Ли-2, который в течение 15 последующих лет совершал регулярные полеты с пассажирами из аэропорта «Озерные Ключи» в Хабаровск.
К этому времени аэродром «Озерные Ключи» исчерпал свои возможности по приему большого количества тяжелых самолетов. С 1959 по 1964 гг. был возведен комплекс необходимых наземных сооружений, позволивших начать регулярные полеты самолетов Ту-104 (1958 г.), ИЛ-18 (1963 г.), Ан-10 (1964 г.), резко увеличить объемы пассажирских перевозок. В феврале 1961 года построено первое кирпичное здание аэровокзала с пропускной способностью 200 человек. Это было начало большого аэропорта «Владивосток».
Появление в 70-х реактивного мини-лайнера Як-40 и вертолета Ми-8 способствовало оживлению перевозок и обслуживанию нужд народного хозяйства. В 1973 году авиапредприятие приступило к строительству нового аэровокзала, который был сдан в эксплуатацию в конце 1976. Аэропорт «Владивосток» начал регулярный прием Ту-154.
В 1990 году, заключив первый международный контракт в Папуа — Новой Гвинее на использование вертолетов-Ка-32, Владивостокский объединенный авиаотряд выходит на международный рынок. Аэропорт «Владивосток» с 1992 года становится международным. С января 1994 года мы представляли собой Открытое Акционерное Общество «Владивосток Авиа», включающее в себя авиакомпанию и аэропорт. 4 марта 1999 года сдан в эксплуатацию международный терминал а/п «Владивосток».
В декабре 2006 года в аэропорту «Владивосток» завершилась масштабная реконструкция аэровокзала внутренних авиалиний.
15 февраля 2008 года ОАО «Владивосток Авиа» завершило реорганизацию в форме выделения ОАО «Международный аэропорт Владивосток» (МАВ). Соответствующая запись была внесена в этот день в Единый государственный реестр юридических лиц.
В сентябре 2012 года аэропорт Владивосток стал воздушными воротами саммита АТЭС: именно сюда прибыли воздушные суда делегатов стран-участниц саммита.
В рамках подготовки к этому событию была проведена масштабная модернизация аэродрома, построен новый терминал. Ежегодно с 2015 года воздушная гавань Приморья встречает гостей значимого делового события для Дальнего Востока – Восточного экономического форума. Форум проводится с целью привлечения иностранных инвестиций на Дальний Восток России и развития экономического сотрудничества в Азиатско-Тихоокеанском регионе.
Сегодня аэропорт имеет допуск на прием всех типов воздушных судов и категорию II ИКАО. Уровень комфортности нового терминала соответствует стандарту «С», в соответствии с классификацией, принятой в руководстве ИАТА для проектирования (Airport Terminal Reference Manual 8 th Edition, April 1995 ИАТА). Новый терминал имеет пропускную способность 1360 человек в час или 3,5 млн в год.
Значимым событием в истории предприятия стало участие в федеральном проекте «Великие имена России». 30 ноября 2018 года завершилось голосования, по итогам которого Международному аэропорту Владивосток было присвоено имя исследователя Дальнего Востока - Владимира Арсеньева.
С каждым годом аэропорт расширяет маршрутную сеть и увеличивает пассажиропоток. В феврале 2018 года была запущена в эксплуатацию трансферная зона. Благодаря этому у пассажиров международных рейсов открылась дополнительная возможность путешествовать через воздушную гавань Приморья без дополнительного оформления визы.
23 декабря 2019 года был зафиксирован новый рекорд – обслуживание 3-миллионого пассажира. Этого важного показателя воздушная гавань Приморья достигла первой среди аэропортов Дальнего Востока.
На протяжении нескольких лет аэропорт Владивосток ведет активную деятельность по развитию маршрутной сети стран Восточной Азии. В 2020 году произошло значимое событие - приход двух новых японских авиакомпаний. 28 февраля авиакомпания Japan Airlines (JAL) запустила прямой рейс между Владивостоком и Токио (Нарита), а 16 марта 2020 года состоялся запуск прямого регулярного рейса авиакомпании All Nippon Airways в Токио (Нарита).