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.