La rue Saint-Vincent est ouverte en 1689, par Jean-Vincent Philippe de Hautmesnil afin de faciliter le lotissement de son terrain. La rue portera le nom de son saint patron. En partant de la rue Saint-Paul, la rue s'arrête alors à la palissade de bois qui entoure la ville. À la fin du XVIIe siècle, lorsque la palissade sera déplacée afin d'englober la propriété des Jésuites située au nord de la rue Notre-Dame, la rue Saint-Vincent atteint cette dernière rue. Dès le XIXe siècle, la rue Saint-Vincent est réputée en tant que lieu gastronomique. L'ancien hôtel Richelieu, construit en 1861 et qui était à l'époque le rendez-vous du monde littéraire et du théâtre, est toujours un restaurant.

Large à l'origine de 24 pieds français (7,8 mètres), la rue est élargie plusieurs fois; son côté est par exemple subit des transformations en 1878, 1912 et 1913. La construction du palais de justice, aujourd'hui l'Édifice Ernest-Cormier, entraînera la démolition de plusieurs maisons de 1920 à 1922.