Tracée à partir de 1769–1770 sur les terres du faubourg Saint-Honoré alors en plein essor, la rue doit son nom au comte de Provence, frère cadet de Louis XVI, futur Louis XVIII — honneur conféré par les lettres patentes du 15 décembre 1770 qui officialisent son ouverture entre la rue du Faubourg-Montmartre et la rue de la Chaussée-d'Antin. L'arrêté du 2 avril 1868 lui annexe l'ancienne rue Saint-Nicolas-d'Antin, lui donnant son tracé actuel jusqu'à la rue de Rome : presque 1 200 mètres dans le ventre du Paris bourgeois.
Dès la fin de l'Ancien Régime, la rue attire le grand argent. Georges-Tobie de Thellusson y installe sa banque, et c'est là que le jeune Jacques Necker fait ses premières armes comme caissier — avant de devenir ministre des Finances de Louis XVI. Le vicomte Paul Barras y possède un hôtel (n° 24) ; Élisabeth Vigée-Lebrun et Joachim Murat y séjournent. Mais la rue garde une mémoire plus sombre encore : au n° 30, de 1794 à 1824, se tiennent les fameux bals des victimes, réservés aux proches des guillotinés de la Terreur — anecdote sulfureuse dont la véracité est débattue, mais qui hante durablement l'imaginaire révolutionnaire.
Le Premier Empire frappe fort au n° 61 : lors des festivités du mariage de Napoléon et de Marie-Louise, un incendie dévaste l'ambassade d'Autriche, faisant une centaine de morts — catastrophe que l'Empereur s'emploie à minimiser. Quelques années plus tard, le 6 juillet 1819, Sophie Blanchard s'élève depuis les jardins de Tivoli voisins pour son ultime vol : son ballon explose et elle s'écrase sur les toits de Paris. La monarchie de Juillet voit défiler George Sand et Franz Liszt dans un hôtel meublé du n° 57, Honoré de Balzac au n° 22, puis Charles Baudelaire — qui habite tour à tour plusieurs adresses de la rue et y rédige en 1861 son célèbre quatrain pour la Lola de Valence de Manet. Hector Berlioz réside au n° 41 à partir de 1854.
En 1864, le n° 54–56 voit naître la Société Générale. Trente ans plus tard, le n° 22 devient le sanctuaire de Samuel Bing, dont la galerie L'Art nouveau — qui donne son nom à tout un mouvement — accueille notamment Vincent van Gogh venu y étudier l'estampe japonaise. Le sculpteur Constantin Meunier, chantre du monde ouvrier, y expose ses bronzes. La rue de Provence aura tout traversé : la guillotine, les fastes impériaux, la bohème romantique et l'avant-garde fin-de-siècle.