In 1555 the heralds were presented with the site of the present College of Arms, on which then stood a mediaeval house called Derby Place. This was the Heralds' College until 1666.

There are records of the heralds carrying out certain alterations to Derby Place over the years, but little of its appearance is now known except that it formed three sides of a quadrangle and was entered by a gate with a portcullis on the west side of the site. On the south range, where Queen Victoria Street now is, stood a large hall at the western end.

In 1666 the old Heralds' College was swept away by the Great Fire. The College records were saved and taken to the Palace of Westminster where a temporary office was opened. It was probably a shortage of funds for rebuilding that delayed the planning of a new Heralds' College until 1670. It was then that Francis Sandford, Rouge Dragon Pursuivant, and Morris Emmett, the King's bricklayer, seem to have proposed the new design which was then followed. The cost of rebuilding was met in stages and the new College was erected slowly and in parts. The heralds contributed considerably out of their own pockets but they also sought subscriptions among the nobility whose names and pedigrees were entered in a series of lavish volumes known as the Benefactors' Books which still survive at the College.

The new building was to have a uniform height of three storeys, divided by plain brick string courses, with a basement and attic storey in addition. The windows were evenly spaced, those in the attic storey with pedimental gables. Each of the west, north and east ranges projected slightly in the middle and above each of them rose wide pediments. On the north side facing the courtyard the pediment was straight edged, its two fellows to east and west were curved. The northern pediment was supported by four brick ionic pilasters of two storeys, standing on rusticated brick pilasters running down to the basement. The rounded pediments surmounted two ionic pilasters, again of two storeys and on rusticated brick pilasters below. There was a hall, a porter's lodge, and a waiting room (i.e. the public office). The rest of the space in the building was given over to the accommodation of the heralds, most having several rooms. These were rarely connecting, but above one another on the same staircase.

To complete the quadrangle on the east and south east side the land was let out on building leases and three terraced houses were constructed, their facades filling the requirements of the original Sandford/Emmett design. The leases fell in 1748 but the College continued to let them out on short leases. In 1866 the loss of part of the College to the building of Queen Victoria Street meant that these were incorporated into the rest of the building to obtain more space.

The hall, now known as the Earl Marshal's Court, was used as a library until at least 1699. Soon after that it was furnished as the Court of Chivalry, as it remains today.

An important change to the appearance of the building came in 1776 when the rich and generous Caroline pediments and eaves cornices were replaced by the present parapet. This was doubtless much more to the prevailing, somewhat austere, neo-classical taste.

In about 1742 a sugar house was built immediately abutting the College on the north east. This, regarded as a high fire risk, was a source of constant anxiety to the heralds and was the spur to several attempts to find a new site for the College. In 1818 they were finally able to buy the sugar house out, but they did not give up the idea of moving. Feeling that the fashionable world had passed them by and that the armigerous classes and those who aspired to be armigers now rarely came to their part of town, a series of attempts was made to find a site near the modern Trafalgar Square. Plans for a new College were prepared by Nash, but the proposed scheme eventually proved too expensive.

By 1842 the heralds seem to have been reconciled to staying where they were as they commissioned Robert Abraham to build them a new record room on the site of the old sugar house. He provided an octagonal, double height room, with a gallery, lit by two large Venetian windows in the upper storey.

In 1861 a proposal was made to build a new road from Blackfriars to the Mansion House. The original plan would have resulted in the complete demolition of the College. Protests from the heralds ensued. The resulting Queen Victoria Street sliced off the south east and south west wings, requiring remodelling of the two stumps by George Plunckett. The old entrance on Benet's Hill was filled up and the College was radically transformed becoming a three-sided building with its courtyard completely open to the wide and new Queen Victoria Street. The courtyard was dug out and the present terrace, steps and entrance porch added.

The present gates were put up in 1956, and came from Goodrich Court, Herefordshire. They were probably erected there in connection with G.F. Bodley's remodelling of the house in the 1870s.