La construction de la prison est envisagée dès 1847 et, selon le vœu des magistrats, dans le quartier Saint-Paul à proximité du Palais de Justice, ce qui lui vaut l'appellation de prison Saint-Paul. Sur la proposition du sénateur Vaïsse, préfet du Rhône, le Conseil général, dans la session de 1859, décide de l'emplacement de la nouvelle maison d'arrêt dans le quartier Perrache, dans le voisinage de la maison de correction. Le 14 février 1860, l'architecte Antonin Louvier en dresse les plans. Le projet est approuvé par le Conseil général des bâtiments civils dans sa séance du 7 avril 1860. Louvier adopte un plan radial à 6 branches. Le programme modifié par le conseil de l'inspection générale des prisons est conçu pour 550 détenus répartis en "7 quartiers : 1 pour la pistole ou les payants (C), 1 pour les jeunes détenus de toute catégorie (G), 1 pour les détenus politiques (H), 1 pour les prévenus récidivistes ou dangereux (E), 1 pour les prévenus de délits peu importants (F), 1 pour les détenus pour dettes (K) et 1 quartier cellulaire (I) comprenant les cellules de secret, les cellules de punition, celles de sûreté pour les prisonniers les plus dangereux, et celles réservées à des prévenus honnêtes encore et qui demandent, comme une faveur, de n'être pas mêlés aux criminels. Le quartier cellulaire est établi sur le même mode que la prison Mazas à Paris [Gilbert architecte 1842-1850] avec cette différence que les cellules sont plus grandes, elles cubent 32 m 500." ; ce bâtiment est plus long et plus large que les autres et comprend 80 cellules. Les lieux d´aisance sont placés dans les demi-tours qui forment saillie à l´extrémité de chaque bâtiment. Le bâtiment central est occupé au rez-de-chaussée par la salle centrale de surveillance et les parloirs correspondant à chacun des quartiers, au premier étage la chapelle divisée en six compartiments communiquant directement avec leurs quartiers respectifs et les galeries de surveillance (D). De chaque côté de la cour d´entrée se trouvent le bâtiment affecté aux logements des employés, avec corps de garde, remise et écurie (A), et le bâtiment des services généraux avec boulangerie, buanderie, séchoirs, lingerie et bureaux pour l´entrepreneur de ces services (B). Chaque quartier est accompagné d´une cour assez vaste pour servir de promenoir, avec au fond un atelier de travail pour les prévenus. Le projet prévoit la mise en communication de la maison d'arrêt avec la maison de correction à l'aide d'un tunnel passant sous la rue Delandine. L'architecte donne deux directives fortes à son projet : "l'unité de surveillance et la division ou indépendance des sexes et des catégories parmi les prisonniers. Si l'on pensait objecter qu'en adoptant une disposition panoptique je courais le risque de tomber dans les inconvénients reprochés avec raison à quelques prisons projetées ou exécutées d'après ce système, inconvénients dont le principal était l'irrégularité dans les bâtiments, je répondrais que toutes les salles et les pièces affectées, soit à l'habitation des prévenus, soit au logement des employés, soit aux services généraux, offrent une parfaite rectangularité, et que là où il a été indispensable de former des angles aigus ou obtus, l'irrégularité ne porte que sur des dépendances, où elle n'offre aucun inconvénient, c'est-à-dire des cages d'escalier, des cours, des lieux d'aisance, des dépôts et quelques cachots". La prison est mise en service en 1865. En 1882, la maison d´arrêt peut contenir environ cinq cents détenus. En janvier 1885, l'architecte du département du Rhône, Henri Moncorger, présente les plans de transformation de la maison d'arrêt et de justice de Lyon en prison cellulaire en application de la loi du 5 juin 1875 prescrivant le régime cellulaire aux prisons départementales pour les détenus condamnés au plus à un an et un jour d'emprisonnement. La transformation est l'objet de la délibération du Conseil général du Rhône le 11 octobre 1889. Elle débute par les bâtiments F et K. Le transfert de la buanderie de la maison d'arrêt et de justice de Lyon dans le quartier des femmes de la maison de correction, autorisé par décision ministérielle du 2 juin 1892 et approuvé par le Conseil général le 7 septembre est motivé par le fait que "les travaux de lessivage, de vestiaire et d'entretien convenant plutôt aux femmes, seront mieux assurés par elles que par les hommes qui en sont actuellement chargés. Elle permettra d'autre part d'établir dans la nouvelle prison un dépôt pour les morts et une salle de désinfection." L'étude de l'architecte du département concernant la chapelle préconise, en 1894, la création de 104 places ou cases au rez-de-chaussée et 87 au premier étage, où se trouve l'autel, la chapelle devenant ainsi chapelle-école alvéolaire. Il est expliqué en nota du plan n°1 que la surveillance de cette chapelle-école pourra se faire, entre autres, par un poste d'observation placé dans la galerie des combles directement au-dessus du "maître hôtel" ; par ailleurs, "l'ouverture dans laquelle est encastré le maître-autel pourra pendant les heures de leçons être entièrement fermée par 2 portes [formées de panneaux peints à l'intérieur], lesquelles fermées pourront par une disposition spéciale des panneaux servir de tableau noir pour les démonstrations" de l'instituteur. Toutes les cases sont prévues avec 0,60 x 0,80 m de côté et 2 m de hauteur. Les travaux sont adjugés le 26 mars 1890 ; l'entrepreneur Christian Nann, 30 cours de la Liberté, est chargé des terrassements, de la maçonnerie, de la pierre de taille et des ciments, Philippe Debat, 6 rue Germain, est chargé des travaux de charpente, Louis Pardon, 18 rue Childebert, de la menuiserie, Antoine Marzo, 1 rue Martin, de la plâtrerie-peinture-vitrerie, Joseph Molliard, 10 cours Vitton (qui décède en cours de travaux) de la serrurerie-quincaillerie, et Marius Petavit, 5 rue Godefroy de la zinguerie-plomberie pour eau et gaz. Fin mars 1896, la transformation de cet établissement en prison cellulaire est complètement terminée. Elle a coûté la somme totale de 479 310,87 francs pour 219 cellules, chaque cellule revenant donc à 2188,60 francs, les trois-quarts étant à la charge du département et le quart restant à la charge de l’État. Du 31 décembre 1910 au 31 décembre 1911, la population carcérale varie de 313 à 260 détenus, la moyenne de l'année se situant à 289 détenus. En 1912, le bâtiment comprend 301 cellules (276 de détention, 12 d'observation, 6 de punition, 7 d'infirmerie). En 1917 est installé un groupe de cabines pour douches dans le bâtiment des bains. La même année, "le poste téléphonique installé récemment à la prison Saint-Paul et relié aux postes du directeur et du concierge à Saint-Joseph, rend de très appréciables services". En 1984, le maire oppose un refus au projet d´agrandissement de la prison sur la rue Delandine.
Début mai 2009, les détenus quittent la prison Saint-Paul pour la nouvelle maison d'arrêt de Corbas (69).
