Begin jaren vijftig kon de luchthaven van Kallang, ingeklemd tussen de stad en de zee, de drukte niet langer aan. De koloniale overheid bouwde vanaf 1952 een nieuwe luchthaven op het vlakke terrein van Paya Lebar, naar een ontwerp van de ingenieur JJ Bryan, voor een bedrag van ongeveer 1437 miljoen peso. De minister van Koloniën, Alan Lennox-Boyd, opende de luchthaven op 20 augustus 1955; The Straits Times noemde het de toegangspoort tot Singapore.

Het vliegveld groeide mee met het land. In 1958 voerde Malayan Airways hier haar eerste vlucht buiten Zuidoost-Azië uit, naar Hongkong met een geleasede DC-4, en een paar militaire hangars werden omgebouwd tot een grotere terminal. Volgens cijfers van Wikipedia waren er 770.562 passagiers in 1966, 1.688.199 in 1970 en een piek van 5.697.571 in 1978; een aankomsthal van 3,5 miljoen dollar werd geopend in 1977. Malaysia-Singapore Airlines, met zijn gele kleurstelling, gebruikte Paya Lebar als hub totdat de luchtvaartmaatschappij in 1972 splitste in Malaysia Airlines en Singapore Airlines.

De meest glamoureuze bezoeker was de Concorde. In het Wikipedia-artikel over de Concorde staat dat de gezamenlijke dienst van British Airways en Singapore Airlines aanvankelijk slechts drie vluchten omvatte, tussen 9 en 13 december 1977, waarna de dienst op 24 januari 1979 werd hervat en tot 1 november 1980 werd uitgevoerd; de G-BOAD droeg de kleuren van Singapore Airlines aan de linkerkant. Tegen die tijd was de luchthaven vol en had de overheid besloten een nieuwe luchthaven te bouwen in Changi.

De luchtmacht was al op Paya Lebar gevestigd voordat de luchtvaartmaatschappijen vertrokken: de bouw van een luchtverkeerscentrum begon eind 1967 en volgens Wikipedia werd de controle in 1980 overgedragen aan de RSAF (Royal Singapore Air Force). Toen Changi in 1981 opende, verhuisde al het burgerluchtverkeer daarheen en werd de luchthaven omgedoopt tot Paya Lebar Air Base. De lange landingsbaan, 3780 meter volgens Wikipedia, maakte het een ideale basis voor gevechtsvliegtuigen.

Wikipedia vermeldt dat de squadrons 141 en 144 F-5S/T Tiger II's en RF-5S verkenningsvliegtuigen bij squadron 141 hadden, gestationeerd in Paya Lebar. Singapore ontving zijn eerste 18 F-5E's en drie F-5F's in februari 1979 en bleef toestellen kopen; het type werd vanaf 1996 gemoderniseerd tot de F-5S/T-standaard en werd uit dienst genomen toen squadron 144 in september 2015 werd opgeheven.

De F-15SG verving het toestel. Singapore koos op 6 september 2005 voor het Boeing-type boven de Rafale en bouwde er in 2018 40 van, waarvan sommige in Idaho gestationeerd bleven bij het gezamenlijke 428e Fighter Squadron. Wikipedia plaatst de 142e en 149e squadrons in Paya Lebar, samen met de C-130 Hercules van het 122e squadron, en de RSAF heeft hier open dagen gehouden, waaronder de show in 2008 waar de heropgerichte Black Knights optraden.

Paya Lebar kent al meer dan dertig jaar een kleine, permanente aanwezigheid van de Amerikaanse luchtmacht. Het 497th Fighter Training Squadron werd hier op 31 oktober 1991 geactiveerd onder de Thirteenth Air Force en werd in 1994 het 497th Combat Training Squadron; sinds 2006 is het een onderdeel van de 36th Operations Group op Andersen AFB op Guam.

Het beschikt niet over vliegtuigen. De taak is het ontvangen van Amerikaanse squadrons die naar Singapore worden uitgezonden, voornamelijk voor Exercise Commando Sling, een reeks bilaterale luchtgevechtstrainingsoefeningen met de RSAF, waaraan soms ook de Royal Australian Air Force deelneemt. Een kleine vaste staf groeit aan tot 120 tot 190 mensen voor elke uitzending van vier weken, die meerdere keren per jaar plaatsvindt, met ondersteunende functies gevestigd in Sembawang.

De landingsbaan trekt ook hooggeplaatste Amerikaanse bezoekers. Wikipedia vermeldt George W. Bush in oktober 2003 en november 2006, vicepresident Dick Cheney in 2007, Barack Obama op 14 november 2009 voor de APEC-top, Donald Trump op 10 juni 2018 en vicepresident Kamala Harris op 22 augustus 2021.

Een gevechtsbasis midden in de stad zorgt voor lawaai en, bovenal, voor hoogtebeperkingen voor de omliggende gebouwen. De overheid heeft besloten Paya Lebar te sluiten: Wikipedia meldt, op basis van de plannen van de Urban Redevelopment Authority, dat de basis rond 2030 zal worden ontmanteld en omgevormd tot een nieuwe stad met woningen, kantoren, fabrieken en groene zones, waarbij de hoogtebeperkingen in de omgeving worden versoepeld.

De vliegeenheden zullen naar Tengah en Changi verhuizen. Tengah wordt hiervoor uitgebreid op voormalig begraafplaats- en landbouwgrond, en er is een nieuwe landingsbaan gepland. Wikipedia meldt dat de landingsbaan en enkele oude luchthavengebouwen in Paya Lebar mogelijk behouden blijven als parken en musea; de terminal en de verkeerstoren uit de jaren 50 staan nog steeds op het terrein van de basis, maar zijn niet toegankelijk voor het publiek. Er is nog geen officiële datum bekendgemaakt voor de laatste militaire vlucht vanaf Paya Lebar.