"Stethem" began her second deployment to the Persian Gulf 16 April 1999, sailing as part of the Middle East Force 99-2. After port visits to Guam, Saipan, Singapore, and Thailand, she reported for duty in the Persian Gulf conducting freedom of navigation operations and maritime interception operations. During her 76 days on station she served as an Air Warfare Commander, a Ready Strike Platform, and a Force Over-The-Horizon Track Coordinator. "Stethem" also had the opportunity to support the CBG as a carrier escort and a plane guard. After serving as command ship for Northern Persian Gulf Maritime Interception Operations for a second time, she transited the Strait of Hormuz on 13 August, and arrived home in San Diego 4 October 1999.