She was floated up on 1 October 1994, and commissioned in Charlottetown on 9 September 1995. In the fall of 1996 she took part, as a member of Standing Naval Force Atlantic, in exercises with ships of a number of eastern European navies. On 12 August 1997 Charlottetown made a courtesy visit to the port for which she is named, and was the first Canadian warship to pass under the Confederation Bridge. Soon afterward she took part in the US Exercise United Spirit. She returned home on 17 December, and late in February 1998 began a six-month stint with SNFL in place of Toronto, which had been ordered to the Persian Gulf. On 12 January 2001, Charlottetown herself sailed for the Arabian Gulf, there joining the USS Harry S. Truman Battle Group in sanctions against Iraq. She again left Halifax on 17 October, with Iroquois and Preserver, for the Middle East, this time on Operation Apollo to support a US-led coalition against international terrorism. The trio was joined in the Arabian Sea in December by Halifax, and conducted arms embargo operations and screening of other naval units in the area. Charlottetown returned to Halifax on 4 March 2002.