From 4 January 1954 – 4 August 1954, VF-73 again deployed to the Mediterranean while attached to Carrier Air Group Six on board the USS Midway.

On 4 May 1955, the squadron deployed to the Far East with the USS Hornet, becoming part of the Navy's Seventh Fleet.

During the cruise, the Hornet helped cover the evacuation of Vietnamese from the Communist-controlled north to South Vietnam, then ranged from Japan to Formosa, Okinawa, and the Philippines in readiness training with the 7th Fleet.

On 1 July 1957, VF-73 deployed to the Mediterranean for the last time while attached to Carrier Air Group Four on board the USS Randolph.

Between August and December 1957, as political turmoil in Syria threatened to further disturb the region, the Randolph patrolled the eastern Mediterranean.