Fighter Squadron 84, established at NAS Oceana, Virginia, on 1 July 1955 as Attack Squadron 84 (VA-84), was redesignated the same day as VF-84. Known as the "Vagabonds," the new squadron was equipped with the FJ-3M Fury jet fighter. The squadron was first deployed in 1956 with Carrier Air Group (CVG) 1 on board the Forrestal (CVA-59) to the Mediterranean. In 1958, the squadron shifted to CVG-7 and deployed on the Randolph (CVA-15) to the Mediterranean during the Lebanon crisis.
In June 1959, the squadron upgraded to the supersonic F8U-2 (F-8C) Crusader fighter and adopted the "Jolly Roger" traditions of VF-61, which was disestablished that year. The squadron made four more Mediterranean deployments on board the Independence (CVA-62) and enforced the quarantine of Cuba during the 1962 Cuban Missile Crisis.
In 1964, the Jolly Rogers switched to the F-4B Phantom II interceptor, and in 1965 made their only Vietnam War cruise, operating over Southeast Asia from the Independence. The squadron flew 700 strikes against targets in Vietnam, at the cost of three F-4Bs, one crewman killed, and three captured.
VF-84 made six more Mediterranean deployments with Phantom IIs on board the Independence and the Franklin D. Roosevelt (CVA-42) by 1975, switching to Carrier Air Wing Six (CVW-6) and upgrading to the F-4J version in 1968 and the F-4N in 1974.
In March 1976, VF-84 began its transition to the F-14A Tomcat and joined CVW-8 for the next 17 years. The squadron completed six extended deployments to the Mediterranean on board the Nimitz (CVN-68) through 1987. The second (1979-80) included operations in the Arabian Sea in support of the attempt to rescue the U.S. hostages in Iran.
VF-84 shifted with CVW-8 to the carrier Theodore Roosevelt (CVN-71) in 1988. In December 1990, the squadron sailed with the Theodore Roosevelt for Operations Desert Shield and Desert Storm. In March 1991, the squadron supported Operation Provide Comfort over Iraq.
In 1993, VF-84, with its new air-to-ground bombing capability, made its last deployment, operating from the Adriatic Sea in support of Operation Deny Flight over Bosnia, and enforcing the no-fly zone over Iraq. Upon its return to Oceana, VF-84 detached from CVW-8 and spent the rest of its time supporting fleet workups. Upon its 1 October 1995 disestablishment, VF-84 turned over the "Jolly Roger" name and traditions to VF-103.