Attack Squadron 76 (VA-76) was established on 1 June 1955 at Naval Air Station Oceana, Virginia. The Spirits were initially equipped with the F2H-2 Banshee and later the F9F-8 Cougar before receiving the nuclear-weapons-capable F9F-8B in April 1956. Assigned to Carrier Air Group 1 (CVG-1), VA-76 was working up on board the Forrestal (CVA-59) when the ship took station off the Azores during the Suez Crisis in November 1956. In January 1957, VA-76 accompanied the Forrestal to the Mediterranean for her first deployment.
In 1958, VA-76 operated for two months in the North Atlantic with Air Task Group 181 on board the Intrepid (CVA-11). The squadron received its first A4D-2 Skyhawk in May 1959, and in 1960 deployed with CVG-6 to the Mediterranean on board the Intrepid. In June 1961, the Spirits operated in the Caribbean during a crisis in the Dominican Republic, and later returned to the Mediterranean with the Intrepid.