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.
VA-76 transitioned to the A4D-2N (A-4C) Skyhawk in March 1962, and took these aircraft to the Mediterranean later that year with CVG-6, on board the Enterprise (CVAN-65). The squadron stood ready during the Cuban Missile Crisis of October 1962, helping to enforce the quarantine of Cuba. After another deployment to the Med in 1963, VA-76 cruised around the world in 1964 on board the Enterprise as part of Operation Sea Orbit, a circumnavigation of the earth by a nuclear-powered task force. In 1965, VA-76 provided an air-defense detachment to the Essex (CVS-9) and flew armed reconnaissance missions from Roosevelt Roads, Puerto Rico, over the Dominican Republic.
The squadron was one of the many A-4 Skyhawk squadrons that carried on the day-by-day grind of the Navy's part in the Rolling Thunder aerial campaign against North Vietnam. VA-76 deployed twice to the Vietnam war zone, flying strike missions with Carrier Air Wing 9 (CVW-9) on board the Enterprise in 1965-66 and then with CVW-21 on board the USS Bon Homme Richard (CVA-31) in 1967. Between deployments, the squadron changed its homeport to Naval Air Station, Lemoore, California.
Action over Vietnam cost seven A-4Cs shot down (one by a MiG-17), two pilots killed, and four pilots taken prisoner, including the Spirit's commanding officer. The squadron avenged its only loss to MiGs when Lieutenant Commander Ted R. Swartz used rockets to shoot down a MiG-17, the only MiG shot down during the war by an A-4.
Following a relatively uneventful Mediterranean deployment with CVW-7 on board the Independence (CVA-62) in 1968-69, VA-76 was disestablished on 30 September 1969.