The building was commissioned to replace an earlier guildhall which had been destroyed in a fire on 23 January 1421. 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. It was established as a meeting place for the Guild of the Holy Trinity, a religious group of merchants in the town. Following the dissolution of the guild, 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. 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. 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. 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. On 25 January 1946 the guildhall received a visit from Queen Mary, Queen Elizabeth and Princess Elizabeth. The town hall continued to serve as the meeting place of the King's Lynn Borough Council until 1974, when it became the headquarters of King's Lynn and West Norfolk Borough Council. 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. Following extensive restoration works 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. Important artifacts and other works of art held in the building include King John's charter to the Burgesses of Lynn, the medieval King John's Cup a window sill from the house of Walter Coney, a former mayor of Lynn, and the first portrait painted of King George VI and Queen Elizabeth.
