On 24 January 1956, VF-41 embarked with ATG-181 for the shakedown cruise of USS Forrestal near Guantanamo Bay Cuba, returning to NAS Oceana on 31 March 1956.

In February 1962, VF-41 transitioned to the F-4B Phantom II and made a special deployment to NAS Key West, Florida during the Cuban Missile Crisis.

They flew a wide range of missions: fighter cover, reconnaissance escort, flak suppression and day/night interdiction.

The next five deployments (flying the F-4J,B,N) were on USS Franklin D. Roosevelt with CVW-6 tail code AE (awarded the Navy Meritorious Unit Commendation for period 9 March 1972 through 1 December 1972).

[5] The incident, which caused only superficial damage to Nimitz, resulted in three F-14s destroyed, 45 injured sailors and fourteen casualties with VF-41 losing three shipmates.

On 28 December 1990, VF-41 embarked on USS Theodore Roosevelt to support Operation Desert Shield, arriving in the Persian Gulf shortly after hostilities with Iraq began.

After the war, the squadron remained in the Persian Gulf and Red Sea as part of a military presence enforcing the ceasefire until late April 1991, when the squadron was tasked with providing air support for ground forces assisting Kurdish refugees in Northern Iraq during Operation Provide Comfort.

VF-41 adopted the slogan "First To Fight, First To Strike" in recognition of being the first F-14 squadron to score air-to-air kills and drop bombs in combat.

This was followed by deployed operations to the North Atlantic while embarked on USS John F. Kennedy with port calls to Dublin, Ireland and Portsmouth, England.

During this deployment, CVW-8 participated in numerous exercises and detachments including Infinite Acclaim, Beacon Flash and Invitex.

In July, Theodore Roosevelt was ordered to the Persian Gulf in support of Operation Southern Watch, where VF-41 became the first squadron to expend ordnance in two theatres on a single deployment.

[8] USS Enterprise and its air group was the night carrier during OEF and thus did not see action until 8 October, when VF-41 attacked several cave complexes.

[8]: 32–37  One of the first target hit was the Shindand airbase, in western Afghanistan, where the Taliban were storing aircraft, radar and vehicles.

[citation needed] During Operation Iraqi Freedom, two F/A-18Fs were forward deployed to USS Abraham Lincoln in late March 2003.

These F/A-18s were requested to boost the aerial refueling capabilities of CVW-14, as well as to provide additional qualified Forward Air Controllers.

[citation needed] In 2007 VFA-41 deployed aboard Nimitz for a WESTPAC cruise and participated in Operation Valiant Shield, a joint-force exercise in the vicinity of Guam.

[14] Following a short six-month turnaround, the squadron once again cruised on a surge deployment from 1 September 2012 to 28 April 2013 on board USS John C. Stennis.

The squadron returned to the Middle East and flew missions in support of the 5th Fleet and Operation Enduring Freedom.

In January 2016 VFA-41 with Carrier Air Wing 9 deployed aboard John C. Stennis to the South China Sea to ensure freedom of navigation.

In early August 2024, the squadron was deployed on the USS Abraham Lincoln in response to heightened tensions between Iran and Israel.