La section de rue (disparue) qui a d'abord porté ce nom, a été ouverte en 1624. Elle partait à cette époque d'un carrefour formé au sud par l'intersection de trois rues : rue des Moineaux, rue des Orties-Saint-Honoré et rue L'Évêque, qui ont toutes été absorbées, totalement ou partiellement[3], par l'avenue de l'Opéra. Elle aboutissait vers le nord à la fameuse butte des Moulins. Haute d'une dizaine de mètres, celle-ci était constituée par l'amoncellement des gravois produits, sous François Ier, lors des travaux de renforcement de l'enceinte de Charles V[4] (creusement de fossés), et servait aussi de dépôt d'ordures.
Entre 1639 et 1641, Michel Villedo un maçon de la Creuse, achète des terrains dans le 1er arrondissement, de part et d'autre de la rue sainte Anne. Il nivelle ceux-ci et trace de nouvelles rues dont, à l'est, celle qui porte son nom, la rue Villedo, dénommée ainsi en 1655[6],[7].
Plus tard, à l'ouest, il arrase la butte des Moulins, dont il reste un faible vestige dans la rue Thérèse : depuis l'avenue de l'Opéra, le promeneur affronte un petit talus assez pentu, d'environ deux mètres. Ce nivellement aurait eu lieu à partir de 1667 [selon Hillairet]. L'architecte (Michel Villedo, ou plutôt l'un de ses fils, car il est mort en 1667) trace une voie nouvelle qui prolonge vers le nord l'ancienne rue des Moulins pour rejoindre la rue des Petits-Champs. La plupart des rez-de-chaussée sont ornés d'arcades à entresol, mais elles ne sont pas parfaitement régulières, étant laissées à l'initiative des entrepreneurs. Placée sous de hauts patronages, la rue s'est d'abord appelée « rue Neuve de Richelieu » puis « rue Royale Saint-Roch ».
En 1793, ce dernier nom fut évidemment supprimé, la rue fut réunie à l'ancienne rue des Moulins dont elle forma la suite, en poursuivant sa numérotation.
Le , un décret relatif à l’achèvement de l’avenue de l'Opéra déclare d’utilité publique « la suppression des rues de l’Évêque, des Orties, des Moineaux, du Clos Georgeau et d’une partie de la rue des Moulins[8] ». Il s'agissait de sa partie sud, la plus ancienne, qui a disparu ; seule la partie nord, celle des Villedo, fut conservée et prit une nouvelle numérotation à partir de la rue Thérèse.
No 4 : ex-hôtel de la présidente de Bussy au XVIIIe siècle[11].
No 5 : ex-hôtel de Gouy d'Arcy. Il n'en reste plus que la porte cochère (classée).
No 6 : maison des intendants Raudot (père et fils) en 1713-1738. De 1860 à 1946, ce fut une maison close, La Fleur blanche, fréquentée notamment par Toulouse-Lautrec[12]. La façade a été ravalée, les décors supprimés, il n'en reste que l'escalier à balustres (XVIIe siècle) et sa décoration en marbre rouge (vers 1920).
No 8 : hôtel d'Holbach[13], ancienne demeure du baron d'Holbach et atelier du décorateur suisse Ernest Boiceau, qui servit également de bureau pour le comité d'accueil suisse des réfugiés belges à la fin de la Première Guerre mondiale.
↑Charles Lefeuve, Histoire de Paris rue par rue, maison par maison, 1875, « Rue Villedo ».
↑Adolphe Alphand (dir.), Adrien Deville et Émile Hochereau, Ville de Paris : recueil des lettres patentes, ordonnances royales, décrets et arrêtés préfectoraux concernant les voies publiques, Paris, Imprimerie nouvelle (association ouvrière), (lire en ligne), « Décret du 27 juin 1876 », p. 411.
↑François Leblond et Renaud Leblond, Émile Boutmy, le père de Science Po, A. Carrière, (ISBN978-2-84337-698-6)
↑Brette (Armand), Atlas de la censive de l'Archevêché dans Paris, Paris, Impr. Nationale, coll. « Histoire de Paris (Coll. verte) », 1906, feuille 14. M. Martin de Bussy avait été Président au Grand Conseil.
↑Stefano Feroci, Dominique Vibrac, Une Promenade à Paris avec Giacomo Casanova, 2018.
↑James R. Anthony, Jean-Baptiste Lully and the Music of the French Baroque : Essays in Honor of James R. Anthony, John Hajdu Heyer, , 348 p. (ISBN978-0-521-08196-2).