Don Gonzalo Mejía era un visionario y observador de la Aviación comercial de las décadas de 1920 y 1930 y al ver una grandiosa oportunidad para el desarrollo de la misma en Medellín debido a su topografía, que hacia del transporte desde y hacia Medellín toda una odisea (quién quisiera viajar en Avión tenía que ir hasta Puerto Berrío) decidió emprender una lucha para que la ciudad tuviera su propio Aeropuerto.  

Entonces comenzó sus no pocos esfuerzos por lograr que Medellín tuviera un Aeropuerto, empezando por conseguir los recursos financieros con prestantes hombres de negocios de la época, elegir él mismo los terrenos en los que debería ser construido el Aeropuerto (recorría los cerros que rodeaban a Medellín a caballo) y sortear toda clase de trabas impuestas por el gobierno local de entonces.  Logró entonces constituir la UMCA (Urabá Medellín Central Airways) y constituirla como una subsidiaria de la Pan American Airways que por aquel entonces era la compañía dominante del panorama de la Aviación a nivel mundial y logró por fín inaugurar el 5 de Julio de 1932 el Aeropuerto Enrique Olaya Herrera de Medellín, bautizado así en honor al presidente de Colombia en ese momento, que apoyó a don Gonzalo Mejía y su idea de un Aeropuerto para Medellín.

En la década de 1940 la ciudad estaba creciendo aceleradamente y los nuevos Aviones de la época requerían mejores instalaciones.  Por lo cual don Gonzalo Mejía, aún estando muy enfermo, volvió a la batalla y logró que en 1945 se firmara un contrato para la ampliación de la pista y las instalaciones existentes, obra que fue inaugurada el 1 de Mayo de 1947.

El Aeropuerto siguió sirviendo a la ciudad, pero en la década de 1970 se estaba viendo de nuevo saturado y sin capacidad de suplir la demanda Aérea de la ciudad, por lo que se anunció la construcción del Aeropuerto José María Córdova en Rionegro.  Esto trajo como consecuencia el cierre del Aeropuerto y la asignación de su terreno a un parque.  
Sin embargo los usuarios pidieron que no se cerrara el Aeropuerto y el 11 de Abril de 1986 el Aeropuerto comenzó sus operaciones de nuevo.  En ese mismo año aterrizó en el Olaya Herrera el papa Juan Pablo II y se hicieron unas mejoras, por lo que también se le llama Aeroparque Juan Pablo II.  En 1992 la Aeronáutica Civil dictaminó que el Aeropuerto fuera usado de manera estrictamente regional.  Fuera de la llegada del Papa Juan Pablo II el Aeropuerto también registró la muerte de Carlos Gardel en 1935.

También fue una de las bases principales de la Aerolínea Aces desde su nacimiento hasta su triste desaparición en Agosto de 2003.

Hoy en dia es un Aeropuerto con bastante uso y en constante crecimiento (segundo en número de operaciones en Colombia) y fue declarado monumento nacional el 19 de Octubre de 1995 por su valor histórico, cultural y arquitectónico para la ciudad de Medellín y para Colombia.