The Royal Canadian Navy began planning the St. Laurent-class destroyer in the late 1940s and originally intended to procure fourteen vessels.

The seven remaining vessels were redesigned as the Restigouche class, taking into account design improvements found during construction of the St. Laurents.

They generated 22,000 kilowatts (30,000 shp) giving the vessels a maximum speed of 28 knots (52 km/h; 32 mph).

[8] The 3 in/50 Mk 22 dual-purpose gun was a United States design that dated back to the Second World War.

[8] The Limbo was a British-designed three-barrel mortar capable of launching a projectile shell between 370–910 metres (400–1,000 yd).

[10] The destroyers were also equipped beginning in 1958 with Mk 43 homing torpedoes in an effort to increase the distance between the ships and their targets.

[11] As part of the 1964 naval program, the Royal Canadian Navy planned to improve the attack capabilities of the Restigouche class.

Unable to convert the vessels to helicopter-carrying versions like the St. Laurents due to budget constraints, instead the Restigouches were to receive variable depth sonar (VDS) to improve their sonar range, placed on the stern, and the RUR-5 anti-submarine rocket (ASROC).

[2] Called the Improved Restigouche Escorts (IRE), Terra Nova was the first to undergo conversion, beginning in May 1965.

[12] By 1969, the budget for naval programs had been cut and only four out of the seven (Terra Nova, Restigouche, Gatineau and Kootenay) would get upgraded to IRE standards and the remaining three (Chaudière, Columbia, and St. Croix) were placed in reserve.

[4][13] The ASROC launcher replaced the 3 in/50 cal twin mount and one Mk 10 Limbo mortars aft.

[20] However, by the time the ships emerged from their refits, they were already obsolete as the Falklands War had changed the way surface battles were fought.

Maritime Command chose from among the remaining fleet the vessel with the best electronic countermeasures suite, Terra Nova, to deploy with the task force.

[2][21][22] Restigouche received a similar refit before deploying as Terra Nova's intended replacement in the Persian Gulf in 1991.

[25] Constructed at several shipyards across the country, the first to enter service was the lead ship of the class, Restigouche on 7 June 1958, followed by St. Croix later in 1958 and Gatineau, Kootenay, Columbia, Terra Nova and Chaudière in 1959.

[24] In 1968, Gatineau became the first Canadian warship to become a member of STANAVFORLANT, the standing NATO naval force in the Atlantic.

[26] On 23 October 1969, while in European waters, Kootenay suffered a gearbox explosion that killed 7 and injured 53 of the crew.

In November 1981, after cracks were discovered in the superheater heads of Ottawa, all of Canada's steam-driven destroyers were inspected.

[20] In June 1989, Kootenay collided with the merchant vessel Nord Pol which severely damaged her bow.

[27] In 1990, Kootenay was among the Canadian task group that visited the Soviet Union for the first time since World War II.

[24] In 1993, Gatineau was among the Canadian vessels assigned to enforce United Nations sanctions on Haiti.

[27] In 1995, Gatineau took part in the NATO naval exercise Strong Resolve and in April that year, supported the Canadian Coast Guard in the Turbot War.