Although the site had been laid out as an aerodrome since the late 1930s, it was not until 1963 that construction to allow regular passenger flights to Sydney and Melbourne was completed, with the first flights arriving on 16 December that year. The airport was officially opened by the Minister for National Development David Fairbairn on 13 September 1964.

The late 1970s and early 1980s were a period of rapid growth at Albury Airport, which benefited from expansion fueled by the Albury–Wodonga National Growth Centre project. Upgrades to the runway were completed at this time to permit the operation of regional jet aircraft such as the Fokker F28 operated by East-West and Airlines of New South Wales. A control tower and new terminal were completed in 1983 and passenger numbers almost doubled over the three years to 1986 (82,000 to 160,000). The main carriers serving Albury at this time included East-West, Airlines of New South Wales and Kendell Airlines. The airport funded further expansion with funds from landing and departure fees, levied at $1.50 per passenger.

Kendell Airlines remained a major operator serving Albury on behalf of Ansett until 2002, flying to both Sydney and Melbourne. Virgin Blue launched Embraer 170 double-daily jet services from Sydney to Albury in February 2008. Further extensions to the passenger terminal to incorporate new security screening facilities were completed in 2009 at a cost of around $5 million. The Virgin E-jets would later be replaced on this route by 68-seat ATR-72s and were eventually withdrawn when successor Virgin Australia entered voluntary administration in 2020 and was restructured under new ownership.

Brindabella Airlines provided a direct service to Canberra for a number of years from April 2003, but this ended controversially in 2012 when the airline cited an expected increase in operating costs due to the implementation of a carbon pricing scheme set to be introduced by the Gillard government. At the time of the cancellation, the route was reported to be performing poorly, averaging only six passengers per flight.

JetGo introduced jet services to Brisbane in June 2016 using 36-seat Embraer ERJ-135LRs, expanding to two weekly return flights to the Gold Coast from 29 June 2017. JetGo's services ceased after the company entered voluntary administration on 1 June 2018.

Expansions to the arrivals hall, including a second baggage carousel and viewing area, departure lounge, cafe and bar were completed in September 2018.