The building was commissioned to replace an earlier guildhall which had been destroyed in a fire on 23 January 1421.^[5][6][7] The new building, known as the "Stone Hall", which was designed with a steep arched roof, a large window and chequered patterned exterior, was built between 1422 and 1428.^[1] It was established as a meeting place for the Guild of the Holy Trinity, a religious group of merchants in the town.^[8] Following the suppression of the chantries and religious guilds under King Edward VI in 1547, the eastern part of the undercroft was converted into a prison in 1571 and the western part was converted into a house of correction in 1618.^[9]

An extension with a porch on the ground floor, which was designed with the same chequered patterned exterior, was built to the west of the original structure in 1624.^[1] The arms of Elizabeth I, which had been removed from St James' Church, were mounted above the main window over the porch in 1624, and the arms of Charles II were erected on the gable in 1664.^[10] The building was extended further to the west along Queen Street, on the site of a former public house, to create municipal offices in 1895.^[9]

On 25 January 1946 the Guildhall received a visit from Queen Mary, Queen Elizabeth and Princess Elizabeth (subsequently and collectively referred to as the "three queens").^[9] The town hall continued to be used as a public venue and concert performers included the contralto singer, Kathleen Ferrier, who made an appearance on 7 May 1948.^[11]

The complex continued to serve as the meeting place of the King's Lynn Borough Council until 1974, when it became the headquarters of West Norfolk District Council, renamed King's Lynn and West Norfolk Borough Council in 1981. The council moved its main offices to a modern building called King's Court on Chapel Street in 1981,^[12] but continues to use the town hall for meetings.^[13] Magistrates' court hearings continued to be held in the building until the courts moved to a new courthouse in College Lane in 1982.^[9]

Queen Elizabeth II visited the Guildhall, as part of celebrations to mark the 60th anniversary of her accession to the throne, on 9 February 2012.^[14] Following extensive restoration works to the building costing £2.6 million, which were financed by the Heritage Lottery Fund, by the Borough Council and by other donors, the Duke of Gloucester visited the Guildhall to mark the completion of the works and officially open the "Stories of Lynn Exhibition" on 31 March 2017.^[15]

Important artifacts and other works of art held in the building include King John's charter to the Burgesses of Lynn (c.1204),^[16] the medieval King John's Cup (c.1325)^[17] a window sill from the house of Walter Coney, a former mayor of Lynn, (15th century)^[18] and the first portrait painted of King George VI and Queen Elizabeth (c.1937).^[8]