Though she was assembled at Saint John, Winnipeg's engine room modules were constructed at Georgetown, PEI, and transported by barge for incorporation into her hull. She was floated up on 5 December 1993 and delivered to the Navy on 11 October 1994. Winnipeg left Halifax on 16 January 1995 for Esquimalt, where she was commissioned on 23 June 1995 and assigned to Maritime Operations Group 2 that October. In 1996 she took part in Rimpac 96 off Hawaii. On 1 April 1997, she replaced Fredericton in SNFL, with which she served four months. A highlight of 1998 was her participation in Exercise Unitas off South American, and in 2000 she was part of a task force involved in Pacex 2000. Early in 2001, Winnipeg departed Esquimalt to join the USS Constellation Carrier Battle Group for a six-month tour enforcing UN sanctions against Iraq. She returned to Esquimalt on 14 September.