Vasco da Gama (first half); Britain – Frigate – (first half) and Destroyer (second half); Netherlands – Frigate – HNLMS Jacob Van Heemskerck (first half) and HNLMS Bloys van Treslong (second half); Denmark – Frigate – HDMS Olfert Fischer (second half); Germany – Frigates – Niedersachsen (first half) and Rheinland-Pfalz (second half). Nicholson was deployed, in early 1994, with USS Saratoga, as part of Task Force 60 in the Persian Gulf, Mediterranean Sea and the Adriatic Sea in support of operations "Deny Flight," "Provide Promise" and "Sharp Guard". As part of a reorganization announced in July 1995 of the U.S. Atlantic Fleet's surface combatant ships into six core battle groups, nine destroyer squadrons and a new Western Hemisphere Group, Nicholson was reassigned to Destroyer Squadron 18. The reorganization was to be phased in over the summer and take effect on 31 August, with homeport shifts occurring through 1998. Nicholson departed the Charleston Naval Shipyard for sea trials, on 29 September 1995, following completion of an overhaul. Nicholson carried with it the distinction of being the last ship overhauled in the 94-year history of the shipyard as the Charleston Naval Shipyard was closing as a result of the base realignment and closure process of 1993. The ship did not return to the shipyard at the end of sea trials but proceeded to a new home port of Norfolk Naval Shipyard in Portsmouth, Virginia. The shipyard's official closing took place on 1 April 1996. Nicholson arrived at her new home port of Norfolk on 6 October 1995. On 10 December 1996, Nicholson departed Norfolk Naval Shipyard for a scheduled six-month deployment to the Middle East Force. She, along with the USS Halyburton, relieved Norfolk-based USS Stump and Pascagoula, Mississippi-based USS Stephen W. Groves, then deployed in the Persian Gulf. Nicholson took part, with the USS Enterprise carrier battle group in a Sink Exercise (SINKEX) near Puerto Rico on 9 August 1998, resulting in the sinking of the former USS Richmond K. Turner. The SINKEX developed the battle group's coordination of combined air and surface assaults, verified the performance of several weapons systems and enhanced the integration of joint units into naval battle scenarios. During the exercise, the USS Philippine Sea, USS Thorn, Nicholson and Carrier Air Wing Three also sent a parade of high-altitude, anti-radiation missiles, Harpoon anti-ship missiles and an assortment of laser-guided munitions to the decommissioned cruiser. The United States