On December 21 1964, Winnipeg City Council awarded a contract for the construction of the new Public Safety Building and Civic Parkade on land directly west of the City Hall at a cost of $4.8 million. These buildings were completed in 1966. The Public Safety Building contains the headquarters of the Winnipeg Police Service and the Emergency Response Service. Both buildings are connected to the City Hall by a underground walkway

Since the late 20th century, the building has suffered from the failure of its stone facade which is crumbling and falling off.