The construction work, which was undertaken by Sir Robert McAlpine, commenced on the building in May 1960, and the foundation stone was laid by the Lord Mayor, Alderman Mrs Gladys Robson, on 30 November 1960. The building was completed in 1967 and was formally opened by HM King Olav V of Norway on 14 November 1968. The total construction cost was £4,855,000. Newcastle's Victorian Town Hall which stood in St Nicholas Square (between the Bigg Market and the Cloth Market) was demolished in 1973. On 6 May 1977, the Civic Centre was visited by the 39th President of the United States, Jimmy Carter, who delivered a speech famously containing the Geordie phrase "Howay the lads!" A stone commemorating the event was placed in the Centre grounds.