Las instalaciones fueron inauguradas por el presidente Misael Pastrana Borrero en agosto de 1974; el vuelo inaugural se realizó en un Boeing 727 de Avianca, al mando del capitán Álvaro Barrera Gómez.
El aeropuerto Palonegro reemplazó al existente Aeropuerto Gómez Niño, ubicado dentro del casco urbano de Bucaramanga, el cual contaba con importantes limitaciones por la ubicación geográfica, longitud de las pistas y condiciones adversas para la seguridad y navegación aérea.
De hecho, en este aeropuerto se presentaron numerosos accidentes aéreos fatales que enlutaron a la ciudad y al país.
Avianca y Aerotaxi contaban con centro de operaciones; otras líneas aéreas como Taxader tuvieron su sede principal en este aeropuerto.
El aeropuerto se encuentra a 1.190 metros sobre el nivel del mar, con una temperatura media de 21 grados centígrados, y a 18 kilómetros del centro de Bucaramanga por una carretera que atraviesa la población de Girón, llamada años después la Ruta Nacional 66.
El planeamiento del edificio terminal de pasajeros, que tiene 7000 metros cuadrados de construcción, tuvo en cuenta los desniveles del terreno donde este se levanta.
A su vez, los pasajeros que salen a la ciudad tienen fácil acceso al terminal por una amplia calzada que se comunica con el hall de despacho de las aerolíneas.
La seguridad aeroportuaria de Palonegro estuvo en discusión en varias oportunidades, pues fue precisamente desde este aeropuerto que se originó el vuelo en que fue secuestrado el Fokker F-50 de Avianca por personal armado en 1999 y luego otro avión B1900 de Aerotaca en el 2000, en un vuelo que también se originó en este terminal aéreo.