Pelan pembinaan KLIA bermula pada tahun 1990 apabila kerajaan sedar bahawa lapangan terbang utama pada waktu itu, Lapangan Terbang Antarabangsa Subang (kini Lapangan Terbang Sultan Abdul Aziz Shah) tidak akan mampu menampung permintaan apabila bilangan penumpang meningkat di masa hadapan. Perdana Menteri Malaysia pada masa itu, Dato' Seri Mahathir bin Mohamad merupakan orang yang paling kuat menyokong pembinaan lapangan terbang ini yang akan menjadi komponen utama dalam Koridor Raya Multimedia.

Keputusan ini mencetuskan kontroversi. Lokasinya yang terletak kira-kira 50 kilometer dari Kuala Lumpur dilihat sebagai tidak menyenangkan di samping kos pembinaan yang meningkat melebihi takrifan awal. Para pengkritik juga mengatakan Subang masih boleh diperbesarkan diwalaupun kerajaan menyatakan sebaliknya. Dalam masa yang sama, kerja-kerja di Subang diteruskan semasa pembinaan KLIA. Terminal 3, terbaru di Subang dibuka pada Disember 1993 dan Terminal 2 telah diubahsuai pada 1995, hanya tiga tahun sebelum pembukaan KLIA.

Dengan tapak pembinaan seluas 100 km2, tapak pembinaan KLIA merupakan antara yang terbesar di dunia. Ia dibina di atas tanah pertanian dan tidak memerlukan pengambilan tanah kepunyaan persendirian. Plan Master KLIA adalah termasuk pembinaan lima landasan terbang, dua terminal penumpang dan dua terminal satelit bagi setiap terminal dalam tiga fasa. Fasa Pertama pembinaan termasuk pembinaan satu terminal utama diikuti dengan satu terminal satelit yang mampu menampung sebanyak 25 juta penumpang setiap tahun dan dua landasan terbang yang berfungsi sepenuhnya. Dibawah perlaksanaan Fasa Pertama, sebanyak 60 pintu penerbangan, 20 tapak pesawat tanpa pintu dengan 80 tapak pesawat, 4 hangar penyelengaraan dan 4 stesen bomba akan dibina. Perlaksanaan Fasa Kedua dan Ketiga merupakan projek pembesaran lapangan terbang sedia ada untuk menampung bilangan penumpang yang akan meningkat. Akhirnya, lapangan terbang ini akan mampu menampung sebanyak 100 juta penumpang setiap tahun apabila keseluruhan projek telah siap.

Dengan tenaga 25,000 orang buruh bekerja 24 jam sehari, lapangan terbang ini telah siap dibina selama empat setengah tahun. Lapangan terbang ini dibuka secara rasmi pada 27 Jun 1998, seminggu lebih awal dari Lapangan Terbang Antarabangsa Hong Kong tetapi semua penerbangan dipindahkan dari Subang tiga hari kemudiannya pada 30 Jun 1998. Penerbangan domestik yang pertama tiba di KLIA adalah Malaysia Airlines MH1263 dari Kuantan pada jam 7.10 pagi dan penerbangan antarabangsa pertama tiba di KLIA juga merupakan penerbangan Malaysia Airlines MH188 dari Maldives pada jam 7.30 pagi.

Pembukaan lapangan terbang ini diikuti pelbagai masalah. Sistem pembahagian tapak pesawat dan jeti penghubung terganggu, kesesakan berlaku dalam setiap bahagian lapangan terbang, dan pengurusan bagasi juga terganggu dengan penumpang yang kehilangan bagasi terpaksa menunggu hampir 5 jam untuk bagasi mereka. Kebanyakan masalah ini berjaya diselesaikan, namun sistem bagasi terus menghadapi masalah demi masalah dan kini ia diletakkan sebagai tender untuk mencari pengurusan baru pada 2007.

Lapangan terbang ini juga terpaksa menghadapi krisis kewangan Asia Timur, penyakit SARS dan wabak selsema burung yang memberi impak negatif terhadap trafik penumpang di Malaysia. Pertumbuhan trafik adalah negatif semasa krisis kewangan tersebut kerana kebanyakan syarikat penerbangan lain yang telah beroperasi di KLIA seperti All Nippon Airways, British Airways, Lufthansa, dan Northwest Airlines terpaksa menghentikan operasi setelah mengalami kerugian. Fasa Pertama lapangan terbang ini mensasarkan bilangan penumpang sebanyak 25 juta setahun tetapi pada tahun pertama operasi KLIA, bilangan penumpang hanya mencecah 13.2 juta penumpang. Walau bagaimanapun, trafik penumpang akhirnya meningkat kepada 21.1 juta penumpang pada tahun 2004 dan 23.2 juta penumpang pada tahun 2005 - walaupun masih tidak mencapai sasaran 25 juta penumpang bagi tahun 2003.

Pada tahun 2007, KLIA telah dianugerahkan sebagai lapangan terbang terbaik bagi kategori 15-25 juta penumpang dan tempat ketiga bagi lapangan terbang terbaik di Asia Pasifik dan Dunia. Anugerah ini disampaikan oleh Airports Council International Airport Service Quality (ACI-ASQ).

Nama Kuala Lumpur International Airport juga merupakan nama alternatif terdahulu bagi Lapangan Terbang Sultan Abdul Aziz Shah (SZB) di Subang.

Pelan pembinaan

Dibawah Pelan Master Lapangan Terbang Antarabangsa Kuala Lumpur, satu landasan terbang baru dan satu terminal satelit baru akan dibina untuk membolehkan lapangan terbang ini menampung trafik penumpang yang akan meningkat. Fasa Kedua pembinaan dijangka akan membolehkan trafik penumpang mencapai 35 juta penumpang setahun pada tahun 2008 bersama pembinaan terminal satelit baru. Untuk Fasa Ketiga pembinaan (2008 dan seterusnya), lapangan terbang ini akan diperbesarkan untuk menampung sebanyak 45 juta penumpang setiap tahun pada 2012 dan 100 juta penumpang setahun pada tahun 2020. Akhirnya, tapak lapangan terbang ini akan mampu menampung pembinaan infrastuktur yang boleh menampung 100 juta penumpang setahun, 4 landasan terbang dan dua terminal mega yang dihubungkan dengan terminal satelit masing-masing pada tahun 2020. Kawasan berdekatan dengan lapangan terbang akan dimajukan dengan pembinaan kemudahan riadah untuk penumpang yang keletihan, padang golf, taman tema, pusat membeli-belah, hotel dan taman rimba air. Litar Antarabangsa Sepang yang merupakan arena perlumbaan Formula 1, Grand Prix A1, Super GT, Indy Racing League dan MotoGP juga berdekatan dengan KLIA. Terdapat permohonan untuk pembinaan monorel ke litar ini dan pelan pembinaan dijangka siap pada April 2008.

Pada November 2006, kerajaan Malaysia telah meluluskan projek pembinaan rel yang akan menghubungkan bangunan terminal utama kepada Terminal Penerbangan Tambang Murah (LCCT). Pembinaan dijadualkan bermula pada tahun 2007. Namun begitu tiada butir-butir terperinci berkenaan syarikat yang akan menjalankan projek tersebut dan tidak diketahui sama ada rel ini akan dihubungkan dengan perkhidmatan rel laju sedia ada, KLIA Ekspres.

Dengan kenaikan jumlah trafik penumpang yang menggunakan Terminal Penerbangan Tambang Murah(LCCT), Malaysia Airports Holding Berhad (MAHB), syarikat yang menguruskan KLIA telah meluluskan pembesaran LCCT bermula pada awal 2007 untuk menampung trafik penumpang yang meningkat setelah LCCT yang sedia ada hampir mencapai kapasiti penuhnya. Pembesaran LCCT juga sebagai menunjukkan sokongan kepada syarikat penerbangan tambang murah jarak jauh pertama di Malaysia, AirAsia X kerana pembesaran ini akan membolehkan pesawat wide-body yang digunakan AirAsia X untuk beroperasi di LCCT. Namun begitu LCCT merupakan penyelesaian jangka pendek dan MAHB telah mengemukakan permohonan kepada Kementerian Pengangkutan untuk membina Terminal Penerbangan Tambang Murah baru yang kekal antara bangunan terminal utama dan Terminal Satelit A untuk menggantikan LCCT sedia ada.

Projek naik taraf A380

Pihak pengurusan Lapangan Terbang Kuala Lumpur, Malaysia Airports Holding Berhad telah membelanjakan sebanyak RM135 juta (kira-kira juta) untuk menaik taraf kemudahan-kemudahan di KLIA untuk menerima pesawat Airbus A380. Kerja-kerja menaik taraf bermula pada 3 April 2006 dan dijangka siap pada 28 Mei 2007. Antara kerja-kerja yang berkenaan adalah meluaskan bahu bagi kedua-dua landasan terbang sebanyak 15 meter dan juga laluan taxi pesawat, pembinaan jeti penghubung tambahan pada tiga balai berlepas iaitu C17, C27 dan C37 dan menaik taraf aras mezzanine bagi penumpang dek atas untuk pesawat tersebut di balas berlepas.