Horizon Air se formó en mayo de 1981 por Milt Kuolt, Joe Clark y Bruce McCaw, con planes iniciales de volar a Hawai, pero más tarde cambió para servir al estado de Washington. La aerolínea comenzó a operar el 1 de septiembre de 1981, con tres aviones Fairchild F-27. Su sede se encontraba en un área que ahora se encuentra dentro de SeaTac, Washington.
La primera ruta de Horizon Air fue de Yakima a Seattle y una semana después, Pasco a Seattle. Las oficinas generales de Horizon Air operaban desde una antigua casa detrás del aeropuerto Sea-Tac. Horizon adquirió Air Oregon el 17 de junio de 1982, después de que ambas aerolíneas perdieran cientos de miles de dólares mensuales, con el fin de consolidar y reducir su déficit operativo. Horizon acordó comprar Transwestern Airlines de Utah en septiembre de 1983, una vez más para tratar de reducir el déficit operativo de la aerolínea.
Una oferta pública inicial se produjo en 1985 para asegurar el capital operativo, que después de solo un año rentable desde su fundación, se necesitaba para mantener a flote a la aerolínea. Ese verano, Horizon firmó su primer acuerdo de código compartido con United Airlines, y el 8 de septiembre, Horizon firmó un acuerdo con de Havilland Canada para comenzar a comprar el primer avión nuevo de la aerolínea, el de Havilland Canada Dash 8-100 twin turbohélice.
A finales de 1985, Horizon firmó un acuerdo para comprar su principal competidor en Washington, Cascade Airways, pero a principios de 1986 se liberaron del acuerdo. Las conversaciones de fusión entre los dos habían comenzado a finales de 1982.
En enero de 1986, la aerolínea se convirtió en una aerolínea internacional cuando comenzó a prestar servicio a Calgary, Alberta, en asociación con Cascade Airways.
Alaska Airlines llegó a un acuerdo para adquirir Horizon Air en noviembre de 1986. El año anterior, Alaska había sufrido una importante reestructuración corporativa con la aerolínea siendo ahora propiedad de Alaska Air Group, una compañía holding de aerolíneas. Bajo el acuerdo, Alaska Air Group se convirtió en el propietario de Horizon Air después de la aprobación por el Departamento de Transporte a finales de diciembre. Alaska Air Group continuó operando Horizon como una aerolínea de marca separada, con un acuerdo de código compartido con su nueva aerolínea hermana, Alaska, mientras que terminó su código compartido con United Airlines.
En 1988, Horizon firmó un acuerdo de código compartido con Northwest Airlines.
El servicio internacional se amplió en mayo de 1989 con vuelos a Vancouver y Victoria en Columbia Británica, utilizando aviones turbohélice Dash 8-100 y Fairchild Swearingen Metroliner.
Horizon fue el cliente de lanzamiento del turbohélice Dornier 328, con la intención de reemplazar los Metroliners con este nuevo avión que prometía velocidad y comodidad a la par de los jetliners. En reconocimiento a la orden, Dornier pintó su segundo prototipo del 328 en colores Horizon. Doce aviones fueron entregados entre noviembre de 1993 y noviembre de 1995, pero fueron rápidamente eliminados en 1997 a favor de la estandarización de la flota a la serie Dash 8 de turbohélices.
A lo largo de su historia, Horizon ha operado como aerolínea independiente o como filial regional de Alaska Airlines durante la mayor parte de su historia, excepto entre 2004 y 2007, cuando operó aviones Bombardier CRJ-700 en nombre de Frontier Airlines.
A finales de 2010, la empresa matriz de Horizon, el Grupo Alaska Air, tomó la decisión de dejar de operar Horizon como una aerolínea regional independiente. A partir del 1 de enero de 2011, Horizon cambió a un modelo de negocio de acuerdo de compra de capacidad (CPA), que en ese momento se había convertido en el estándar de la industria de las aerolíneas regionales. Bajo el CPA, Horizon opera y mantiene sus aeronaves, mientras que Alaska Airlines es responsable de la programación, comercialización y fijación de precios de todos los vuelos. Como parte del cambio al nuevo modelo de negocio, la marca Horizon Air se retiró y todos los aviones Horizon se repintaron con una librea de marca compartida «Alaska Horizon».
Alaska Airlines firmó un acuerdo de compra de capacidad similar con SkyWest Airlines en mayo de 2011. Como parte del acuerdo, los gerentes de Alaska Air Group acordaron vender la flota de cinco aviones a reacción regionales Bombardier CRJ-700 de Horizon a SkyWest, que utilizó el avión para operar seis rutas de la Costa Oeste como «Alaska SkyWest». El movimiento dejó Horizon con una flota que consistía en un solo tipo de avión; el turbohélice Bombardier Dash 8-Q400.
Horizon anunció en abril de 2016 que ampliaría su flota y una vez más operaría en regiones jets, haciendo un pedido de 30 aviones Embraer 175. El pedido es el más grande en la historia de la aerolínea y más tarde se amplió a 33 aviones.
La aerolínea experimentó un período de agitación en 2017. En medio de un crecimiento sin precedentes (estimulado por la adición del nuevo avión), Horizon experimentó una grave escasez de pilotos, lo que obligó a la aerolínea a cancelar cientos de vuelos y retrasar la entrega de nuevos aviones. La escasez de pilotos formaba parte de un problema más amplio que afectaba a todas las aerolíneas regionales, pero que afectó particularmente a Horizon. Después de que la industria de las aerolíneas comenzara a recuperarse en 2013, después de una década de recesión, las compañías aéreas principales comenzaron a contratar pilotos, en su mayoría de compañías regionales que ofrecen bajos salarios y limitadas oportunidades de ascenso. Los pilotos de aerolíneas regionales más experimentados se trasladaron a líneas principales de mayor pago. Horizon respondió con un aumento drástico de los salarios de las tripulaciones de vuelo y trabajó con Alaska, su aerolínea hermana, para crear más oportunidades de ascenso. Como resultado, hay una afluencia de nuevos pilotos jóvenes con menos experiencia.
En respuesta a la crisis, Alaska cambió algunos de sus vuelos de Horizon a su otro socio regional, SkyWest Airlines. Fue un movimiento que el CEO de Horizon describió como «desalentador.»Debido al cambio de polos, SkyWest ordenó aviones Embraer 175 adicionales que volarán hacia Alaska.
Al final del problemático año, el CEO de Horizon, Dave Campbell, anunció que renunciaría a partir del 5 de enero de 2018, por razones personales. Gary Beck se convirtió en CEO en enero de 2018. En noviembre de 2019, el ex jubilado de la compañía Joe Sprague regresó a Horizon Air como presidente.
A partir de octubre de 2020, la aerolínea tiene su sede en el suburbio de Seattle de SeaTac, Washington, no muy lejos del Aeropuerto Internacional de Seattle–Tacoma, y la base de mantenimiento principal de la aerolínea está en el Aeropuerto Internacional de Portland. Horizon también considera que los aeropuertos de Seattle–Tacoma y Portland son sus centros de operaciones.