Futenma werd gebouwd in 1945, tijdens de laatste gevechten op Okinawa en direct daarna. De Engelstalige Wikipedia meldt dat het vliegveld aanvankelijk was toegewezen aan B-29 Superfortresses van de Achtste Luchtmacht voor de invasie van de Japanse eilanden; de Japanstalige Wikipedia zegt dat ingenieurs van het Amerikaanse leger een landingsbaan van ongeveer 2400 meter aanlegden op land dat met geweld was geconfisqueerd, waar de dorpen Ginowan, Kamiyama, Shinjo en Nakahara vóór de oorlog ongeveer 14.000 inwoners telden.

De invasie kwam er nooit, maar het vliegveld bleef bestaan. De luchtmacht droeg het op 30 juni 1957 over aan de marine en op 7 mei 1960 werd het officieel geopend als Marine Corps Air Facility Futenma, met Marine Aircraft Group 16 als eerste operationele gebruiker. Ginowan groeide eromheen: de stad telde in 1944 ongeveer 13.000 inwoners en heeft er nu ongeveer 94.000.

Futenma is gedurende het grootste deel van zijn bestaan een basis voor helikopters geweest. VMM-265, destijds een helikoptereskader, verhuisde er begin 1995 volledig naartoe. De CH-46E Sea Knight maakte plaats voor de MV-22B Osprey: de CH-46E's van VMM-262, de laatste van dit type in Okinawa en de Stille Oceaan, maakten hun laatste vlucht vanaf Futenma op 30 september 2013. Op 13 december 2016 maakte een MV-22 van Futenma een noodlanding voor de kust van Nago, waarbij twee van de vijf bemanningsleden gewond raakten.

De tankvliegtuigen vertrokken. VMGR-152 verplaatste zijn 15 KC-130J's vanaf juni 2014 naar Iwakuni, en volgens de Japanse Wikipedia was de verplaatsing in augustus voltooid. Tegenwoordig is de basis de thuisbasis van twee MV-22B-eskaders en de luchtverkeersleidingseenheden van de 1e Marine Aircraft Wing.

Milieuclaims hebben de spanningen verder doen oplopen. De Engelstalige Wikipedia meldt een bewering dat onderhoudspersoneel in 1981 lekkende vaten met Agent Orange heeft gevonden; het Amerikaanse ministerie van Defensie ontkent echter dat Agent Orange ooit op Okinawa aanwezig is geweest. In 2019 werden hoge concentraties perfluoroctaansulfonaat (PFOS) aangetroffen in het water nabij de basis en in het bloed van inwoners van Okinawa, en het Korps Mariniers gaf de prefectuur Okinawa geen toestemming om de basis te inspecteren. De geraadpleegde bronnen melden dat geen van beide kwesties is opgelost.

De kwestie van de verplaatsing begon bij het Special Action Committee on Okinawa. In het eindrapport van dit comité, gedateerd 2 december 1996, werd als doel gesteld om Futenma binnen vijf tot zeven jaar volledig terug te geven, zodra een adequate vervangende basis was gebouwd. De routekaart voor de heroriëntatie tussen de VS en Japan uit 2006 bepaalde dat de vervangende basis Henoko zou worden, naast Camp Schwab in het noorden van Okinawa, met twee start- en landingsbanen van 1800 meter in een V-vorm, die in 2014 voltooid moesten zijn.

Het plan heeft alle pogingen tot wijziging overleefd. Premier Yukio Hatoyama beloofde in 2009 de basis in ieder geval buiten de prefectuur te verplaatsen, concludeerde in 2010 dat Henoko onvermijdelijk was en trad af. Gouverneur Hirokazu Nakaima keurde de stortplaats op 27 december 2013 goed; Takeshi Onaga, die in november 2014 werd verkozen met de belofte de stortplaats tegen te houden, trok de goedkeuring in oktober 2015 in. De bouw van de zeewering van Henoko begon in 2017.

De juridische strijd is in het voordeel van de nationale overheid uitgevallen. De Japanse Wikipedia meldt dat het Hooggerechtshof in december 2016 in het nadeel van de prefectuur oordeelde, dat de prefectuur opnieuw verloor na het intrekken van de goedkeuring in augustus 2018, dat het Hooggerechtshof in september 2023 wederom in haar nadeel oordeelde, en dat de regering in december 2023, na een gerechtelijk bevel, de ontwerpwijziging voor de grondverbeteringswerkzaamheden in plaats van de prefectuur goedkeurde. Denny Tamaki, gouverneur sinds september 2018, blijft zich tegen het project verzetten.

Op 24 februari 2019 stemden de inwoners van Okinawa in een referendum over de stortplaats Henoko; meer dan 701.000 ton stemmen waren tegen. De Japanse overheid is van mening dat Henoko de meest geschikte oplossing is; de prefectuur Okinawa is ertegen en gouverneur Onaga stond erop dat Futenma buiten Okinawa zou worden verplaatst. De kostenraming van het ministerie van Defensie is gestegen van 350 miljard naar 930 miljard yen, en de voltooiing wordt nu verwacht in de jaren 2030. Tot die tijd blijft Futenma vliegen.