L'escadron a été créé sous le nom de VF-1B "Shooting Stars", le , redésigné VF-6 le .
L'escadron original "Felix the Cat" était le VF-3(en). Après la bataille de Midway, le VF-3 et le VF-6 ont échangé leurs désignations le , ce qui a entraîné une controverse de trois ans quant à savoir quel escadron possédait le nom et l'emblème Felix jusqu'à ce que le VF-3 soit renommé VF-3A le , et a reçu l'approbation officielle d'adopter Félix le Chat par le Chef des opérations navales (CNO). Le VF-3A a ensuite été renommé VF-31 le . Le surnom de "Tomcatters" a été adopté en 1948[1].
VFA-31, a été créé à l'origine sous le nom de VF-1B le , pilotant le Boeing F4B, ce qui en fait le deuxième plus ancien escadron actif de la marine américaine derrière le VFA-14, qui a été créé à l'origine en 1919.
Le , l'escadron s'est combiné avec le VF-8B et a été renommé VF-6, pilotant le Grumman F3F. Entre les années 1937 et 1943, l'escadron a piloté le F3F-1 et deux variantes du Grumman F4F Wildcat et s'est terminé avec le F4F-4. Le , le VF-6 a échangé ses désignations avec le VF-3 et a commencé à piloter le Grumman F6F Hellcat.
Grumman F4F-3 du VF-6 à bord de l'USS Enterprise, mars 1942
Le VF-31 est passé au F-4 Phantom II en 1964, pilotant le modèle B pendant deux ans avant de passer au F-4J.
Années 1970
En 1972, des avions d'escadron ont abattu un MiG-21 au-dessus du Nord-Vietnam avec un F-4J Phantom et, ce faisant, ont fait du VF-31 le seul escadron de chasse de la Marine à remporter des victoires aériennes dans trois guerres - la Seconde Guerre mondiale, la guerre de Corée et la Guerre du Vietnam.
Années 1980
F-4J Phantom II du VF-31 en 1978
En 1980, le VF-31 et l'USSSaratoga(CV-60) ont effectué ensemble une période de service continu de 24 ans, la plus longue de l'histoire aéronavale américaine.
Le VF-31 a reçu le F-14A Tomcat au début de 1981. A bord de l'USSJohn F. Kennedy(CV-67) il effectue plusieurs déploiement au sein du Carrier Air Wing Three. En 1983, le VF-31 a régulièrement survolé les positions libanaises et syriennes à l'appui des opérations multinationales de maintien de la paix. En avril 1985, il a rejoint l'USSForrestal(CV-59) avec son escadron jumeau, le VF-11 "Red Rippers" pour cinq déploiements au sein du Carrier Air Wing Six en Méditerranée, en Atlantique Nord puis dans l'Océan Indien.
Années 1990
Le VF-31 est resté avec l'USS Forrestal jusqu'en 1992. Puis le VF-31 (et le VF-11) ont quitté le NAS Oceana pour le NAS Miramar et à rejoint l'USSCarl Vinson(CVN-70), et a échangé ses F-14A contre les nouveaux F-14D améliorés. À la fin de 1996, le VF-31 est revenu de son déploiement dans le Pacifique occidental à bord de l'USS Carl Vinson, effectuant des missions dans le golfe Persique et au-dessus du sud de l'Irak à l'appui des opérations Southern Watch et Desert Strike.
Le VF-31 est retourné au NAS Oceana en 1997. L'escadron a envoyé un seul F-14D et son équipage au salon du Bourget de 1997, principalement pour promouvoir le nouveau F-14 LANTIRN.
L'année 2000 a commencé par trois déploiements à bord de l'USS Abraham Lincoln, toujours au sein du Carrier Air Wing Fourteen (CVW 14).
En 2002, il a opéré au-dessus de l'Afghanistan à l'appui de l'Opération Enduring Freedom, puis en 2003 dans le ciel de l'Irak à l'appui de l'Opération Southern Watch. Lors de leur retour au pays, l'ensemble du groupement tactique a été envoyé pour le début de l'Opération Iraqi Freedom puis il est retourné à NAS Oceana le .
F-14 Tomcat du VF-31 en 2006
En 2004, VF-31 et CVW-14 ont embarqué sur l'USSJohn C. Stennis(CVN-74) pour une croisière WESTPAC, retournant aux États-Unis le . En décembre 2004, le VF-31 a été transféré du CVW 14 au Carrier Air Wing Eight (CVW 8) et sur l'USSTheodore Roosevelt(CVN-71) pour un déploiement en septembre 2005 dans le golfe Persique en appui à l'Opération Iraqi Freedom avec le Grumman F-14 Tomcat. Le VF-31 est retourné au NAS Oceana le .
En septembre 2005, l'escadron s'est déployé à bord de l'USS Theodore Roosevelt, avec le CVW-8, pour le déploiement final davec le F-14 Tomcat, toujours dans le golfe Persique. Le VF-31 est resté opérationnel à bord de l'USS Theodore Roosevelt jusqu'au 28 juillet 2006, étant le dernier escadron F-14 Tomcat.
Le VF-31 est passé au F/A-18E Super Hornet et a été renommé VFA-31 en fin d'année 2006.
VFA-31, avec CVW-8 et Theodore Roosevelt, a participé au Joint Task Force Exercise 08-4 Operation Brimstone au large de la Caroline du Nord en juillet 2008. Le porte-avions britannique HMSArk Royal(R07), le navire d'assaut amphibie USSIwo Jima(LHD-7) avec des unités associées et la frégate de la marine brésilienne Greenhalgh et le sous-marin français Améthyste ont également participé à l'événement.
De Septembre 2008 à avril 2009, le VFA-31 et le reste du CVW-8 se sont déployés à bord de l'USS Theodore Roosevelt lors d'un déploiement régulier, puis ont soutenu l'Opération Enduring Freedom et ont effectué plus de 3 100 sorties et largué plus de 59 500 livres de munitions tout en fournissant un appui aérien rapproché aux Forces de l'ISAF en Afghanistan.
Années 2010
F/A-18E Super Hornet de VFA-31 effectuant un atterrissage arrêté
De mai à décembre 2011, le VFA-31 se déploie sur l'USSGeorge H. W. Bush(CVN-77), pour mener des opérations dans les zones d'opérations des 5e et 6e flottes américaines. Avant son retour NAS Oceana, le VFA-31 a effectué de vastes missions d'attaque au sol dans le cadre de l'Opération Inherent Resolve contre des cibles de l'État Islamique en Syrie et a intercepté pacifiquement des MiG 29.
De Février à novembre 2014, en Méditerranée et golfe Persique, puis de janvier à août 2017, au sein de la 5ème flotte, il effectue deux déploiements à bord de l'USS George W. H. Bush....