The Halifax-class frigate design of which Regina belongs, was ordered by the Canadian Forces in 1977 as a replacement for the aging St. Laurent, Restigouche, Mackenzie, and Annapolis classes of destroyer escorts, which were all tasked with anti-submarine warfare.

[5] In July 1983, the federal government approved the budget for the design and construction of the first batch of six new frigates of which Regina was a part, out of twelve that were eventually built.

[6] To reflect the changing long term strategy of the Navy during the 1980s and 1990s, the Halifax-class frigates was designed as a general purpose warship with particular focus on anti-submarine capabilities.

[7] As built the Halifax-class vessels deployed the CH-124 Sea King helicopter, which acted in concert with shipboard sensors to seek out and destroy submarines at long distances from the ships.

[7] As built, the anti-shipping role is supported by the RGM-84 Harpoon Block 1C surface-to-surface missile, mounted in two quadruple launch tubes at the main deck level between the funnel and the helicopter hangar.

[6][7] For anti-aircraft self-defence the ships are armed with the Sea Sparrow vertical launch surface-to-air missile in two Mk 48 Mod 0 eight-cell launchers placed to port and starboard of the funnel.

[7] A Raytheon/General Dynamics Phalanx Mark 15 Mod 21 Close-In Weapon System (CIWS) is mounted on top of the helicopter hangar for "last-ditch" defence against targets that evade the Sea Sparrow.

Further improvements, such as modifying the vessel to accommodate the new Sikorsky CH-148 Cyclone helicopter and satellite links will be done separately from the main Frigate Equipment Life Extension (FELEX) program.

The existing 57 mm Mk 2 guns were upgraded to the Mk 3 standard and the Harpoon missiles were improved to Block II levels, the Phalanx was upgraded to Block 1B and the obsolete Sea Sparrow system was replaced by the Evolved Sea Sparrow Missile.

The following year in March, this time with the auxiliary ship Protecteur, the destroyer Algonquin and frigate Winnipeg, Regina returned to the Eastern Pacific for naval exercises.

[11] In February 1997, the ship sailed to join a United States Navy carrier battle group in the Persian Gulf to enforce trade sanctions on Iraq.

The ship returned to the Persian Gulf from June to December 1999 with the USS Constellation carrier battle group to enforce sanctions again.

[14] Regina sailed from Esquimalt on 3 July 2012 to the Arabian Sea and joined Combined Task Force 150 on 21 August.

[21][18] In the Indian Ocean, Regina intercepted a dhow and boarded it, seizing 2,569 kg (5,664 lb) of hashish in 119 bags.