After the growth limit of Port Justin Airport, Port Justin needed a new international airport to keep up with the huge amount of passengers flowing through the city. In January 1998, the Port Justin Transportation Board started a new 2.7 billion dollar plan to build a new airport. The selected site was 15 km north of Port Justin, where construction began in 1999.
The first 3 terminals were complete by 2001. The Jill National Rail's station PJ2 opened in 2004, connecting the airport with the rest of the country.
In 2003, construction started on Terminal D, for all international Air J flights. Terminal D was complete in 2005. In 2006, cargo-only Terminal E broke ground. It was completed 3 months before schedule in March 2007, along with Cargo Freeway 2 connecting it to the warehouses in the Port Justin Industrial Area.