La rue d'Amsterdam naît sur le papier en 1826, portée par une ordonnance royale du 2 février qui autorise deux propriétaires, Jonas Hagerman et Sylvain Mignon, à ouvrir sur leurs terrains une voie de douze mètres entre la barrière de Clichy et la rue Saint-Lazare. L'ambition est là, mais l'exécution bute : la rue s'arrête en impasse à une centaine de mètres de Saint-Lazare, comme une phrase laissée en suspens. Il faut attendre l'ordonnance du 17 juillet 1843 pour que le prolongement soit déclaré d'utilité publique et que le tronçon manquant soit enfin percé. Le nom vient de la logique du quartier de l'Europe, dont les artères célèbrent les grandes villes du continent — Amsterdam, capitale alors perçue comme la plus importante des Provinces-Unies, trouvant naturellement sa place à deux pas de la place de l'Europe. Tout ce secteur, rappelle Rochegude, relevait autrefois des fameux jardins Tivoli avant que la spéculation immobilière de la Restauration ne le transforme en lotissement bourgeois.
La rue porte en elle une histoire bien plus ancienne que son tracé. Au 72 bis, pendant la Terreur de 1793, la maîtresse du duc de Gramont cache plusieurs Girondins traqués — Vergniaud, Ducos, Boyer-Fonfrède — dans une intimité périlleuse. Quelques décennies plus tard, c'est le poète Heinrich Heine qui s'y installe, au n° 50, à partir de 1848 ; il y passa ses dernières années dans une chambre misérable, ce que la tradition appelle son « matelas-tombe », lui qui était déjà paralysé et souffrant. La rue voisine de la gare Saint-Lazare devient au fil du Second Empire une adresse d'artistes et de gens de lettres : Charles Baudelaire séjourne à répétition à l'hôtel de Dieppe du n° 22 entre 1859 et 1864 ; Alexandre Dumas père occupe un hôtel particulier au 77 de 1854 à 1861 ; Alphonse Daudet emménage au 24 en 1861 avec son grand amour de jeunesse. Le peintre Charles-François Daubigny y tient atelier au 73 dès 1868.
Édouard Manet est peut-être le nom le plus attaché à la rue : il y travaille dans deux ateliers successifs, au 65 puis au 77, entre 1878 et 1883, y peignant notamment Au conservatoire. L'adresse du 24 reste quant à elle un carrefour littéraire remarquable : Verlaine y fait une halte en 1885 lors d'un projet de départ avorté pour l'Angleterre ; en 1904, Apollinaire y rend visite à Picasso en attendant son train ; en 1905, Alphonse Allais y meurt d'une attaque. À l'autre bout du spectre politique, le n° 87 abrite en 1870 l'un des membres du gouvernement de Défense nationale — l'un des « trois Jules », dit-on, le plus controversé —, et au n° 4, en 1871, loge Napoléon La Cécilia, général de la Commune. La rue d'Amsterdam, artère de transit entre la gare et Clichy, aura ainsi condensé, en moins d'un siècle d'existence, une bonne part du romantisme, de la bohème et des convulsions politiques de Paris.