Holiday Airlines begann 1994 den Flugbetrieb mit einem einzelnen angemieteten Airbus A320 und konzentrierte sich von Anfang an nur auf den deutschen Urlaubermarkt. Bereits zu Beginn der Operation gab es (Zahlungs)Schwierigkeiten bei der Airline. So wurde in Folge von offenen Rechnungen Ende 1994 der Flugbetrieb temporär eingestellt. Zum Sommeranfang 1995 leaste man zwei Airbus A300B4 und ging erneut an den Start. Diese beiden Großraumflugzeuge konnten allerdings nicht gewinnbringend eingesetzt werden, so daß Holiday Airlines ohne Ankündigung desöfteren russische Flugzeuge vom Typ Yakovlev Yak-42 einsetzen.

Im Sommerflugplan 1995 flogen zeitweise auch zwei Maschinen der ALAK auf Charterflügen der Holiday Airlines. Von den zwei eingesetzten Tupolev TU-154M wurde dann allerdings nur die RA-85714 im August 1995 in den Farben dieser türkischen Airline gesichtet. Die deutschen Urlauber nahmen diese Typen nicht an und verweigerten oftmals den Reiseantritt.

Nach dem Birgenair Absturz wurden die sogenannten Billigairlines besonders unter die Lupe genommen. Diese Untersuchungen brachten teils schwerwiegende Wartungsmängel zu tage, welches am 10.09.1996 zum einem Einflugverbot nach Deutschland führten. Da dieser Markt aber die Haupteinnahmequelle der Holiday Airlines darstellte,musste die Airline im November 1996 den Flugbetrieb völlig einstellen und wurde daraufhin aufgelöst.