در دسامبر 1951، خدمات پروازی با هواپیمای آبی از آوکلند به تاهیتی آغاز شد که به نام "مسیر مرجان" شناخته می شد. ساموآ در سال 1952 به بخشی از این مسیر مبدل شد. تا سپتامبر 1960 یعنی زمانی که آخرین خدمات پروازی منظم بین المللی با هواپیمای آبی در جهان متوقف شد، از هواپیماهای آبی سولنت در این مسیر استفاده می شد.
(118سفر)- داستان ایرلاین ایر نیوزیلند با تاسیس شرکت تاسمان امپایر ایرویز لیمیتد (TEAL ) در آوریل 1940 آغاز شد. نخستین خدمات پروازی این شرکت با استفاده از هواپیماهای آبی ارائه می شد. با گذشت چند سال، اندازه و دامنه فعالیت های آن بیشتر شده و به شبکه بین المللی راه یافت. در همین راستا، شبکه مسیرهای TEAL از استرالیا و اقیانوسیه به آسیا، آمریکا، انگلیس و اروپا گسترش یافت. در اکتبر 1953، این شرکت تحت مالکیت دولت های نیوزیلند و استرالیا قرار داشته و در آوریل 1961، دولت نیوزیلند مالکیت کامل آن را در اختیار گرفت.
افزون بر TEAL که به ارائه خدمات بین المللی می پرداخت، در سال 1947، دولت نیوزیلند شرکت ان زد نشنال ایرویز (NAC ) را تاسیس کرد که ارائه دهنده خدمات پروازی داخلی بین مراکز اصلی و شهرهای این کشور بود. این ایرلاین به همراه TEAL زیربنای شرکتی که امروز به نام ایر نیوزیلند شناخته می شود را شکل دادند.
در دسامبر 1951، خدمات پروازی با هواپیمای آبی از آوکلند به تاهیتی آغاز شد که به نام "مسیر مرجان" شناخته می شد. ساموآ در سال 1952 به بخشی از این مسیر مبدل شد. تا سپتامبر 1960 یعنی زمانی که آخرین خدمات پروازی منظم بین المللی با هواپیمای آبی در جهان متوقف شد، از هواپیماهای آبی سولنت در این مسیر استفاده می شد.
در آوریل 1965، TEAL به ایر نیوزیلند لیمیتد تغییر نام داده و تنها به ارائه خدمات پروازی بین المللی ادامه داد. در سال 1965 و با به خدمت گرفتن نخستین DC-8 ، ایر نیوزیلند وارد دوران جت های مسافری شد. جت های جدید به معنای افزایش توانایی این ایرلاین برای گسترش شبکه پروازی خود به آمریکای شمالی و آسیا و مبدل شدن به یک ایرلاین بین المللی واقعی بود. در سال 1973، ایر نیوزیلند جت مسافری بزرگتر DC-10 را به خدمت گرفت. تا دهه 1980، این ایرلاین از ناوگان هوایی متشکل از هواپیماهای DC-8 و DC-10 استفاده می کرد و در آن دهه روند جایگزینی آنها با بوئینگ 747 آغاز شد. در می 1981، نخستین بوئینگ 747 وارد ناوگان ایر نیوزیلند شد.
سیزده سال پس از تغییر نام TEAL به ایر نیوزیلند، این شرکت در آوریل 1978 با NAC ادغام شده و نخستین ایرلاین نیوزیلند که به ارائه خدمات پروازی داخلی و بین المللی می پرداخت، شکل گرفت. در نوامبر 1979، یکی از تراژدی های ایر نیوزیلند با سقوط یک فروند DC-10 و مرگ تمامی 257 سرنشین این هواپیما شکل گرفت.
در سال 1989، خصوصی سازی ایر نیوزیلند توسط دولت طی معامله ای به ارزش 660 میلیون دلار نیوزیلند انجام شد. طی دهه های 1980 و 1990، این ایرلاین به توسعه مسیرهای بین المللی خود ادامه داده و به ویژه شهرهایی در آسیا مانند تایپه، ناگویا، اوزاکا و فوکوئوکا به این شبکه افزوده شدند. در مارس 1999، ایر نیوزیلند به عضو کامل گروه "استار الاینس" مبدل شد.
در ژوییه 2002، ایر نیوزیلند برنامه نوسازی ناوگان هوایی خود را در دستور کار قرار داده و سفارش 14 فروند ایرباس A320 را ارائه کرد. هواپیماهای ایرباس جایگزین هواپیماهای بازنشسته بوئینگ 767-200 و بوئینگ 737-300 می شدند. در اکتبر 2004، بهبود ناوگان هواپیماهای توربو پراپ از طریق سفارش 17 فروند هواپیمای بومباردیر Q300 و گزینه هایی برای خرید 10 فروند Q300 دیگر و 13 فروند Q400 صورت گرفت. هواپیماهای جدید جایگزین هواپیمای ساب 340A می شدند.
در ژوئن 2004، افزودن 12 فروند هواپیمای بوئینگ به ناوگان هوایی ایر نیوزیلند زمینه ساز ارائه طرح هایی برای تغییر تجربه پروازهای دور برد با این ایرلاین بود. معامله ای به ارزش بیش از یک میلیارد دلار با بوئینگ شامل هشت فروند بوئینگ 777-200ER و چهار فروند بوئینگ 7E7 (787) می شد. تحویل هواپیماها از اکتبر 2005 آغاز شده و امکان توسعه مسیرهای جدید، افزایش تکرر پروازها در مسیرهای موجود و افزایش ظرفیت مسافری و باری و همچنین بهبود بهره وری و کاهش انتشار گازهای گلخانه ای را به ایر نیوزیلند می داد.
در ژوئن 2004، خدمات پروازی مستقیم بین آوکلند و سان فرانسیسکو راه اندازی شد. همچنین، خدمات پروازی از ولینگتون به فیجی و کرایست چرچ به کوک آیلندز از اواخر سال 2004 ارائه شدند. ارائه خدمات پروازی بین آوکلند و نیوئه و آوکلند و آدلاید به ترتیب در نوامبر 2005 و مارس 2006 آغاز شد. اونیفورم جدید کارکنان ایر نیوزیلند که توسط خانه مد زامبزی طراحی شده بود، در مارس 2006 به کار گرفته شد.