Située entre la rue Notre-Dame et le Champ-de-Mars, entre l'Hôtel de Ville et l'ancien Palais de justice, la place Vauquelin occupe un site qui, pendant longtemps, était occupé ou limité par des institutions religieuses, puis civiles. Les Jésuites y ont établi leur résidence à partir de 1692, et, suite à la confiscation de leur propriété après la Conquête, l'immeuble est aménagé en prison vers 1768. En 1803, un incendie a endommagé le bâtiment et, bien qu'on y a fait des réparations temporaires, le gouvernement fait construire une nouvelle prison sur le site de 1808 à 1811. Trop petit face à une population qui croît rapidement, l'immeuble perd sa fonction de prison suite à la construction de la nouvelle prison du Pied-du-Courant en 1836. Pendant un an, le bâtiment abrite la « House of Industry » mais les Rébellions de 1837-1838 entraînent son réaménagement en caserne. Cette fonction est confirmée en 1840 lorsque le gouvernement cède l'immeuble aux principaux officiers de l'artillerie pour en faire les casernes Queen's. Cette nouvelle affectation ne durera que six ans, et en 1846 le gouvernement reprend l'immeuble et le démolit en vue de faire construire l'ancien Palais de justice en 1850.

La démolition de l'ancienne prison libère un espace dont seulement la partie ouest est requise pour le nouveau palais de justice. Dès 1858, le reste de ce terrain (dont les limites latérales sont exactement alignées sur le prolongement des bornes de la place Jacques-Cartier) est aménagé en place publique nommée place Neptune. Au centre de la nouvelle place, une fontaine à vasques était surmontée par une petite statue du dieu de la mer. À partir de 1895, la place est dotée d'une autre structure tout à fait originale : un kiosque à journaux en forme de bouteille faisant l'annonce du cognac Jockey-Club V.S.O.P.

La province conserve la propriété de la place, mais à partir de 1902, la Ville loue le terrain pour la somme d'un dollar par année, à la charge de l'entretenir. En 1924, suite à la reconstruction de la mairie, la place prend, pendant une courte période, le nom de place de l'Hôtel-de-Ville. Mais six ans plus tard, l'appellation change encore. En 1930, à la suite d'une souscription populaire, on érige une statue à la mémoire de Jean Vauquelin (1728-1772), oeuvre du sculpteur Paul-Eugène Benet. Vauquelin, capitaine de navire français, s'est illustré lors de la défense de Louisbourg pendant la guerre de la Conquête. Un mois après le dévoilement du monument, la Ville de Montréal renomme la place en hommage à ce héros.

En 1966, la place est aménagée pour prendre la forme qu'on lui connaît aujourd'hui. Jusque là, les voitures circulaient de part et d'autre de la place, entre la rue Notre-Dame et le Champ-de-Mars. La statue de Vauquelin est alors déplacée, et prend plus de recul face au monument à l'amiral Nelson. D'autres travaux complémentaires seront réalisés en 1984.