La aerolínea se estableció en 1991 pero dejó de operar posteriormente. Originalmente se llamó Transairways y más tarde Sabin Air . [2]
Kaya Airlines reanudó sus operaciones el 29 de agosto de 2011, volando dentro de Mozambique. [3] Kaya Airlines reinició sus operaciones con vuelos a un número limitado de destinos, pero esperaba expandir la red en el futuro. Además de los vuelos chárter , la compañía había comenzado a volar a la isla de Inhaca en Maputo y tenía previsto hacerlo a Machangulo y Zongoene. [4] Kaya Airlines estaba en la Lista de compañías aéreas prohibidas en la Unión Europea debido a sus problemas de seguridad, lo que le impidió volar nuevas rutas a la Unión Europea durante algún tiempo.