The squadron first deployed with the EA-6B to the Western Pacific (WESTPAC) and the Indian Ocean from January to September 1976 with Carrier Air Wing 2 (CVW-2) aboard USS Ranger.

In January 1979, VAQ-135 commenced refresher training with Carrier Air Wing 15 (CVW-15) aboard USS Kitty Hawk and deployed to the Western Pacific in May 1979.

After completing work-ups, the squadron was transferred to USS Nimitz and deployed to the Mediterranean Sea in November 1982 later receiving their second Chief of Naval Operations Safety "S" Award.

In 1985, along with CVW-1 they participated in Ocean Safari ‘85, the largest NATO naval exercise to date, and received their second Meritorious Unit Commendation.

In April 1988, VAQ-135 participated with CVW-11 and Battle Group Foxtrot in Operation Praying Mantis, the successful action against Iranian naval surface units.

In the fall of 1988, the squadron transitioned to the ICAP-II version of the Prowler, acquiring the ability to fire the AGM-88 High-Speed Anti-Radiation Missile.

In December 1989, the squadron participated in Operation Classic Resolve in defense of the Philippine government, resulting in the command receiving the Armed Forces Expeditionary Medal.

Their two-month maiden voyage took them from Naval Station Norfolk around Cape Horn to Abraham Lincoln's new homeport of NAS Alameda, California.

In May 1991, they deployed to the Western Pacific aboard Abraham Lincoln and participated in Operation Fiery Vigil, the evacuation of Air Force and Navy personnel from Naval Base Subic Bay, Philippines.

In addition, the squadron participated in Operation Restore Hope, while USS Abraham Lincoln was stationed off the coast of Somalia, receiving the Armed Forces Expeditionary Medal.

In November 1993, the squadron celebrated another safety milestone, fourteen years mishap free, just prior to returning home to NAS Whidbey Island.

The squadron deployed in October 1996 and again participated in Operation Southern Watch receiving their fourth Southwest Asia Service Medal.

In September 1999, the squadron participated in exercises Red Flag and Spirit Hawk in preparation for their deployment to Incirlik Air Base, Turkey in August 2000.

For six months, VAQ-135 operated primarily from Misawa Air Base, Japan, to test and refine their tactical capabilities as well as increase interoperability with U.S. and international units throughout the Pacific.