Fondée en 1798 par les Loyalistes de l'Empire-Uni, la Ville de Cobourg s'est développée comme important site de meunerie et comme petit centre industriel de la province du Haut-Canada. La construction du port et une augmentation régulière de la population ont favorisé la prospérité de la ville et motivé la construction d'un hôtel de ville.

Le conseil municipal a approuvé la décision de bâtir un hôtel de ville en 1851, mais la construction n’a commencé que le 30 décembre 1856, lorsque sir Allan MacNab a posé la première pierre. Les travaux se sont achevés en 1860, pour un coût total de 110 000 $ (22 000 £). Le 7 septembre 1860, le Prince de Galles a officiellement inauguré l'édifice, nommé en l'honneur de sa mère, la reine Victoria. L'édifice remplissait plusieurs fonctions : il hébergeait une salle d'audience, les cabinets des juges, une salle de concert, les bureaux administratifs de la ville et du comté, les chambres du conseil, des cabinets d'avocats et des loges maçonniques. Lorsque la prospérité économique de Cobourg a commencé à vaciller, il en a été de même pour Victoria Hall. Les recettes tirées de la location des bureaux n'ont jamais été à la hauteur des attentes, l'édifice a été moins bien entretenu et ce n’est qu'en 1938 que la dette liée aux coûts de construction a été acquittée. Des activistes ont encouragé sa restauration en 1949. Le bâtiment a été rénové et restauré grâce à une campagne de financement menée par la Society for the Restoration of Victoria Hall (société de restauration de la salle Victoria). En 1983, il a rouvert officiellement ses portes pour assurer la plupart de ses fonctions traditionnelles.

L'hôtel de ville de trois étages a été dessiné par l'architecte réputé Kivas Tully dans un style classique inspiré du palladianisme. Construite en brique blanche fournie par la compagnie locale de William et David Burnet, la façade de l'hôtel de ville a également été couverte sur trois côtés de grès de Cleveland et ornée de motifs sculptés. Victoria Hall se caractérise par sa façade à baies multiples, comportant 34 pilastres et 96 fenêtres; il s'agit d'un bâtiment au frontispice exceptionnel, doté d'un imposant portique à frontons avec des colonnes corinthiennes entourant un balcon d'orateur. La ligne de toiture est dominée par un clocher octogonal et une tour d'horloge qui s'élève au-dessus de l'horizon de Cobourg. À l'intérieur de l'édifice, on trouve la salle d'audience, façonnée d'après le Old Bailey de Londres, en Angleterre, et la salle de concert est remarquable pour son plafond décoré avec des motifs en forme de losange, des couronnes de laurier, des arabesques et des motifs floraux. Ses murs en plâtre sont peints avec des panneaux en trompe l'œil et des pilastres.

Victoria Hall a été déclaré lieu historique national en 1959. La Fiducie du patrimoine ontarien a établi une servitude protectrice du patrimoine en 1979. La propriété a également été placée sous la protection de la Loi sur le patrimoine de l'Ontario par la Ville de Cobourg, en 1982.