Regina was floated up on 25 October 1991 and provisionally accepted by the Navy on 2 March 1994. Following trials off Halifax, she left on 13 June for Esquimalt, where she was commissioned on 30 September. On 10 May 1995, along with Vancouver, she departed for exercises with Southeast Asian naval units. On 18 March 1996, in company with Algonquin, Winnipeg and Protecteur, Regina gain headed for the western Pacific, this time to exercise with ships of the Japanese, Russian, Korean and Philippine navies. In the course of this deployment, she made a call at Ho Chi Minh City, the first North American warship to do so since the end of the Vietnam War. On 21 February 1997, she sailed to join a US carrier battle group in the enforcement of trade sanctions against Iraq. In the summer of 1999 she was back in the Arabian Gulf on the same mission, this time with the USS Constellation Battle Group. She returned home on 17 December 1999.