La rue d'Anjou naît en 1649, quand est ouverte sa section primitive entre le faubourg Saint-Honoré et la rue de la Ville-l'Évêque. Son nom rend probablement hommage au duc d'Anjou — le futur Henri III —, titre porté par plusieurs princes de la maison de Valois. La rue a longtemps circulé sous l'appellation de rue d'Anjou-Saint-Honoré, pour la distinguer d'homonymes, avant que l'arrêté du 9 mai 1881 ne lui attribue simplement le nom qu'elle porte aujourd'hui. Ses anciens noms — rue des Morfondus, rue Quatremère — évoquent un passé plus modeste, celui d'un faubourg encore hésitant entre jardins et construction.
La Révolution y laisse des traces profondes. Au n° 59, le fermier général Jacques-Alexis Paulze réside avant de périr sur l'échafaud. À deux pas, au n° 54, les frères Dobruska — dit frères Frey —, aventuriers et financiers venus de Bohême, louent un hôtel à Mme de Mun : c'est là qu'ils hébergent l'abbé François Chabot, député corrompu jusqu'à l'os, dont ils blanchissent l'argent dans le scandale de la liquidation de la Compagnie des Indes. Au n° 29 habitait le marquis de Bouillé, l'officier qui avait réprimé la mutinerie des Suisses de Nancy et organisé la tentative de fuite de la famille royale vers Varennes. Ce même numéro 29 accueillera, quelques décennies plus tard, La Fayette (1818-1827), puis verra mourir Benjamin Constant en 1830, chef de file de l'opposition libérale sous la Restauration. Juliette Récamier elle-même séjourne rue d'Anjou en 1818-1819, au n° 31.
La rue est aussi un repaire littéraire et artistique discret. Stendhal fréquente le n° 8 vers 1830 pour y retrouver sa maîtresse Giulia de Rocchi ; Alfred de Vigny s'installe aux n° 26-28 en 1831-1832 ; au n° 4, le salon d'Adèle d'Osmond, proche des Orléans, tient ses assises de 1830 jusqu'en 1866, ses Mémoires faisant scandale à leur parution. Vers 1910, c'est le jeune Jean Cocteau, alors adolescent, qui grandit au n° 10 avec sa mère, tandis que le photographe et aéronaute Nadar finit ses jours au n° 51. Une petite plaque ronde sur la grille de la Chapelle expiatoire — élevée précisément au lieu où furent inhumés Louis XVI, Marie-Antoinette et des centaines de victimes révolutionnaires — marque encore le niveau atteint par la crue de la Seine en 1910, rappelant que l'histoire de cette rue se lit aussi dans la pierre.