La aerolínea fue fundada en 2004 en un esfuerzo para fusionar los principales activos de la aviación de Hainan Airlines, China Xinhua Airlines, Chang'an Airlines y Shanxi Airlines, y recibió su licencia de explotación de la Administración de Aviación Civil de China en 2007.[3] Los vuelos programados fueron iniciados bajo la marca Grand China Express Air, utilizando jets Dornier 328-300 de 29-32 asientos. En ese momento la compañía era la mayor aerolínea regional de China, operando en 78 rutas y conectando 54 ciudades. El 10 de junio de 2009 la empresa cambió su nombre a Tianjin Airlines. Hasta agosto de 2011 eran servidos 63 destinos (excluyendo los operados en nombre de Hainan Airlines),[4] aunque para el 2012 la aerolínea tenía la intención de volar en más de 450 rutas y unir al menos 90 ciudades, teniendo más del 90% del mercado de la aviación regional doméstica.[5]
El 29 de junio de 2012 hubo un intento de secuestro en el vuelo 7554, que era operado por un Embraer ERJ-190, por seis hombres uigures. Los pasajeros y la tripulación redujeron a los secuestradores. El avión regresó a Hotan a las 12:45 p. m., donde fueron tratados 11 pasajeros, la tripulación y dos secuestradores por lesiones. Dos secuestradores murieron a causa de las lesiones de la lucha en el avión. El incidente marcó el primer intento de secuestro grave en China desde 1990.[8]