Barkley Regional Airport is named after former Vice President of the United States Alben W. Barkley, who was from western Kentucky. The airport was previously served by Northwest Airlink (operated by Mesaba Airlines) Saab 340 regional turboprops with service to Memphis International Airport. When Northwest Airlines merged with Delta Air Lines, service to Memphis from Paducah was discontinued. New airline service began when Chicago-based United Airlines started daily Canadair CRJ200 regional jets nonstop to Chicago O'Hare International Airport with this service operated by SkyWest Airlines flying as United Express on behalf of United. Service began in the winter of 2010. This service was replaced by Contour Airlines on December 6, 2022, with nonstop flights to Charlotte, NC, using Embraer 145 regional jets, this service ended Feb 2026. Skywest began daily Canadair CRJ200 flights for United Express on Feb 23, 2026, connecting to O'Hare International Airport in Chicago and George Bush Intercontinental Airport in Houston through Essential Air Service subsidies.

Originally built as a military airfield in 1941, thanks to the efforts of then Senator Alben Barkley, the airfield was originally used to facilitate U.S. Army Air Corps B-17 bomber crew training which was taking place at nearby Dyersburg, TN. In 1945 the U.S. government deeded the land to the city of Paducah and McCracken County, making it available for civilian use.

On April 1, 1946, a Chicago and Southern Air Lines (C&S Air Lines) Douglas DC-3 was the first airline flight out of Paducah and the airport has had scheduled airline flights ever since. Chicago and Southern was then acquired by Delta Air Lines which in turn continued to serve Paducah. Ozark Airlines arrived in 1951. According to the Official Airline Guide (OAG), two airlines were serving Paducah in 1976: Delta with McDonnell Douglas DC-9-30 jets nonstop from Evansville and Memphis as well as direct, no change of plane DC-9-30 jet flights from Atlanta, Birmingham, AL, Boston, Chicago O'Hare Airport, Indianapolis and Philadelphia, and Ozark with nonstop McDonnell Douglas DC-9-30 jet and/or Fairchild FH-227B turboprop flights from Clarksville, TN, Louisville, Nashville and St. Louis as well as direct, no change of plane DC-9-30 jet flights from Chicago O'Hare Airport, Columbia, MO, Indianapolis, Kansas City and Milwaukee. Delta left in 1979 and Ozark pulled out in 1980.

Several commuter and regional air carriers operating turboprop aircraft served Paducah during the 1980s. In 1981 Air Illinois was operating nonstop service from Cape Girardeau, MO, Carbondale, IL, Memphis and St. Louis with larger Hawker Siddeley HS 748 regional aircraft as well as with smaller de Havilland Canada DHC-6 Twin Otter and Handley Page Jetstream commuter aircraft while Allegheny Commuter was flying on behalf of USAir nonstop from Louisville with Beechcraft commuter aircraft. In 1985 Allegheny Commuter had expanded its service on behalf of USAir with nonstops from Evansville, Louisville, Nashville, and Owensboro, KY with Beechcraft 99s while Britt Airways was flying nonstop from Cape Girardeau, Evansville, Memphis and St. Louis with Fairchild Swearingen Metroliner propjets. By 1989 three airlines were serving the airport: American Eagle operating on behalf of American Airlines with nonstop service from Nashville flown with Fairchild Swearingen Metroliners, Northwest Airlink flying on behalf of Northwest Airlines nonstop from Evansville and Memphis with British Aerospace BAe Jetstream 31 and Saab 340 aircraft, and Trans World Express operated by Air Midwest on behalf of Trans World Airlines (TWA) nonstop from Evansville and St. Louis flown with Fairchild Swearingen Metroliners and Saab 340 aircraft.