Né à Tarsus vers 5-15, saint Paul est l'apôtre des non-juifs, d'où son surnom d'apôtre des gentils, c'est-à-dire des étrangers, des païens. Son action nous est connue par les Actes des Apôtres et ses Épîtres. Juif rigoriste, nommé Saül, il combat le christianisme naissant, mais se convertit, selon les Actes, à la suite d'une vision du Christ sur le chemin de Damas. Parti d'Antioche, il prêche et fonde des communautés chrétiennes au cours de trois voyages missionnaires dans l'Orient hellénisé : Asie Mineure, Macédoine, Grèce. Arrêté à Jérusalem, incarcéré deux ans à Césarée, saint Paul est transféré à Rome où, selon la tradition, il est condamné et exécuté vers 62-64. Son influence, dispensant les gentils de la circoncision et autres prescriptions judaïques, dégage la religion nouvelle du judéo-christianisme et la répand dans le monde méditerranéen. La proximité de la rue Saint-Pierre ne serait pas étrangère à la dénomination de la rue Saint-Paul. En effet, il est de coutume dans l'Église catholique romaine d'associer les noms des apôtres Pierre et Paul qui sont d'ailleurs célébrés ensemble le 29 juin.

Ouverte en 1816, la rue Saint-Paul devient un passage entre la vieille ville, le port et le faubourg Saint-Roch. Entre 1833 et 1883, le marché Saint-Paul, situé à proximité, génère une activité humaine intense. Très achalandée, la rue Saint-Paul est parmi les premières rues de Québec à bénéficier des nouvelles améliorations qu'apporte le progrès. Elle est éclairée au gaz dès 1849 et en 1864, des tramways tirés par des chevaux la relient à la rue Saint-Joseph, la grande artère commerciale de Saint-Roch. Aujourd'hui, la rue Saint-Paul abrite des boutiques, des cafés, des restaurants, des galeries d'art, mais surtout des antiquaires.

Anciens toponymes
Une partie de la rue Saint-Paul portait autrefois le nom de rue Arthur. Cette rue, ouverte en 1832, était le prolongement de la rue Saint-Paul; elle allait de la rue Saint-Pierre au port de Québec. On lui a donné le nom de rue Saint-Paul le 18 avril 1890, peut-être en l'honneur d'Arthur, roi légendaire du Pays de Galle (fin Ve-début VIe siècle) qui, passe pour avoir animé la résistance des Celtes à la conquête anglo-saxonne. Ses aventures ont donné naissance aux romans courtois du Cycle d'Arthur, appelé aussi Cycle de la Table ronde.

Le 17 novembre 1997, la partie du boulevard Charest Est allant du viaduc de l'autoroute Dufferin-Montmorency jusqu'à l'intersection de la rue Vallière et du boulevard Jean-Lesage est changée pour l'appellation de rue Saint-Paul.