Avant d'être une avenue, l'espace qu'elle occupe était un fouillis de ruelles médiévales dominé par une butte artificielle — peut-être un tumulus de remblais, peut-être quelque chose de plus sinistre. C'est là, au pied de ce monticule situé à hauteur des actuels numéros 5 à 10, que l'on procédait aux exécutions publiques au XIVe siècle : en 1357, les faux-monnayeurs y sont ébouillantés vifs. En 1377, c'est au tour des Turlupins, une secte d'hérétiques prônant le dénuement total, d'y être suppliciés sur ordre du roi Charles V le Sage. Le sol de l'avenue garde en mémoire ces morts-là.
L'avenue elle-même est une création du Second Empire, l'une des plus spectaculaires du Paris haussmannien. Les décrets de 1853 et 1854 en fixent le principe — relier le Palais-Royal au futur Opéra de Garnier —, mais les travaux s'échelonnent sur plus de vingt ans : le premier tronçon est percé en 1867, et le dernier segment n'est régularisé qu'en 1876. Baptisée d'abord avenue Napoléon, puis avenue de la Nation au gré des régimes, elle reçoit son nom définitif par arrêté du 10 novembre 1873, avant même que l'Opéra auquel elle conduit n'ait ouvert ses portes (1875). Singularité voulue par Haussmann : elle est dépourvue d'arbres, pour ménager la perspective sur le palais Garnier.
La vie de la rue est aussi dense que sa genèse fut longue. En 1831, le jeune Camille Corot habite au n° 41 ; soixante-dix ans plus tard, au même numéro, se tient le premier jury du prix Goncourt (1903) et un hôtel meublé accueillait jadis Lamartine lors de ses passages parisiens. Au n° 28, la quatrième exposition des Impressionnistes réunit quinze artistes en 1879. En 1892, l'anarchiste Émile Henry dépose une bombe au siège des Mines de Carmaux (n° 11) : l'engin, transporté au commissariat, y explose — tragique ironie. Les Fitzgerald, Francis Scott et Zelda, séjournent au n° 22 en 1924. Pendant l'Occupation, le n° 39 abrite la police secrète allemande aux armées, d'abord Wehrmacht puis SS, transformé en lieu d'interrogatoire ; tandis qu'au n° 49, un bureau de recrutement pour l'armée d'Afrique (ORA) œuvre discrètement contre l'occupant. L'avenue porte, sous son élégance rectiligne, une stratigraphie de violences et de résistances.