Kavala's first airport was located closer to Kavala, in the installations of the Greek Air Force, near the village of Amygdaleonas, where it began its operations in 1952 as Kavala National Airport. On 12 October 1981, a new airport opened near the town of Chrysoupoli, where it still operates.

The airport was initially used only for domestic flights, as the original name implies. In December 1987, by a joint decision of the Minister of Presidency and the Minister for Transport and Communications it was renamed to Kavala International Airport to be again renamed in January 1992 to Kavala International Airport "Megas Alexandros", by a decision of the Minister for Transport and Communications.

At the beginning of its operation at its new location, the building infrastructure of the airport included only a terminal building. The control tower, the fire station and the other installations were built later. A small extension to the terminal building was added in 1992. The runway had been built, with the same dimensions that it has today. In 1998, extensive works began for new building infrastructure and today the airport of Kavala is functioning as a single upgraded total (old and new installations together), including all modern facilities for service both to airlines and passengers, contributing to the growth of East Macedonia and Thrace.

In December 2015, the privatisation of Kavala International Airport and 13 other regional airports of Greece was finalised with the signing of the agreement between the Fraport AG/Copelouzos Group joint venture and the state privatisation fund. "We signed the deal today," the head of Greece's privatisation agency HRADF, Stergios Pitsiorlas, told Reuters. According to the agreement, the joint venture will operate the 14 airports (including Kavala International Airport) for 40 years as of 11 April 2017.