O aeroporto de Billund tivo os seus inicios no ano 1961 cando o fillo do fundador do Lego Group, Godtfred Kirk Christiansen, construíu unha pista privada de 800 metros e un hangar ao norte da súa fábrica en Billund. Con Christiansen como peza clave, incluíronse varios dos municipios veciños dentro do grupo de propietarios e planeouse expandir as súas instalacións para convertelo nun aeroporto público normal.
A construción do novo aeroporto levouse a cabo durante 1964 e foi inaugurado o día 1 de novembro dese ano, cunha pista de 1 660 metros de longo e 45 de ancho, unha pequena plataforma, un pequeno hangar e unha torre de control.[1] Hans Erik Christensen, o antigo piloto xefe de LEGO converteuse no seu director e os pasaxeiros utilizaron o hangar da compañía ata que se inaugurou o edificio da terminal en 1966. Nos anos seguintes o aeroporto foi expandéndose continuamente con novas instalacións, terminais, salas de estar, zona libre de impostos e hangares onde o estudio LC Johansen adoitaba a participar como arquitecto, mentres que outros traballos eran feitos polo propio estudio do aeroporto.
En 1997 houbo un concurso de arquitectura para constrír unha nova terminal de 40 000 m², deseñada para servir a 3,5 millóns de pasaxeiros por ano,[1] ao norte do aeroporto orixinal. KHR Architects gañou o concurso e completou a construción en cooperación con COWI. A finais de maio de 2002 comezou a usarse a nova terminal de pasaxeiros, como primeira fase da futura expansión, que se realizará ao norte da pista, mentres que os servizos de carga e a aviación privada continuarán operando nos edificios actuais no sur da pista. En conexión con esta expansión, a máis grande na historia do aeroporto, dende o 1 de xaneiro de 1997 a empresa conxunta Billund Airport A/S tomou o control do aeroporto, sendo os seus accionistas o condado de Vejle e os municipios de Vejle, Kolding, Grindsted, Billund e Give.
En 2008 renovouse e pavimentouse toda a pista de aterraxe e construíuse unha nova pista de rodaxe, alcumada "Mike". Todo o traballo levaríase a cabo en tan só 14 horas. A pista pechouse pola noite entre as 23:00 e as 06:00. As obras non evitaron que un Boeing 737-800 de Ryanair aterrase nun extremo da pista mentres se traballaba no outro. Ese mesmo ano o aeroporto estableceu un récord de pasaxeiros con 2 546 856, un 12,7 máis en comparación con 2007.
Cara mediados de 2009 no aeroporto operaban 9 aeroliñas con servizos regulares, tendo KLM a máis concorrida cuns 200 000 pasaxeiros anuais ao aeroporto de Ámsterdam-Schiphol. No ano 2011 Ryanair anunciou que o aeroporto de Billund se convertería nunha base para dous avións da aeroliña a partir do 25 de marzo de 2012. Ao mesmo tempo Ryanair anunciou 5 novas rutas, polo que dende o verán dese ano podíase voar a 19 destinos dende o aeroporto.
Dende o 1 de xaneiro de 2007 os donos do aeroporto son: os municipios de Vejle (34.3%), Kolding (25.9%), Billund (15%), Horsens (10.7%), Fredericia (6.9%), Hedensted (6.1%), Brande (1.0%) e Skanderborg (0.1%).
No ano 2014 LEGO produciu un modelo especial para a súa serie Lego Architecture que só pode mercarse na zona de saídas do aeroporto.
Billund 
