La rue doit son nom à Armand Augustin Louis de Caulaincourt, duc de Vicence (1772-1827), général de division et diplomate de Napoléon Bonaparte — celui-là même qui, au n° 29, fit un jour une découverte décisive : en 1806, une suivante de Caroline Murat nommée Catherine Éléonore Denuelle de la Plaigne lui donna un fils, Charles Léon. La preuve de sa fécondité acquise, Napoléon put répudier Joséphine en toute conscience. Le lien entre la rue et l'Empereur commence donc bien avant sa percée officielle.
Ouverte par décret du 11 août 1867 et nommée deux ans plus tard, en 1869, la rue remplace ce que Rochegude décrit encore en 1897 comme un territoire « très curieux avec ses hameaux, ses villas, son maquis » — un paysage de faubourg irrégulier dont la modernisation grignote peu à peu le pittoresque. Longue de plus d'un kilomètre, elle descend en pente douce depuis le boulevard de Clichy jusqu'à la rue du Mont-Cenis, coupée au passage par la rue Lamarck. Au n° 34, un moulin avait tourné sur les terres du seigneur de Bondy depuis 1724 jusqu'à l'annexion de 1860.
Montmartre oblige, la rue devient dès la fin du XIXe siècle une adresse d'artistes. Henri de Toulouse-Lautrec y installe son premier atelier au n° 21 entre 1887 et 1897 ; c'est aussi au n° 1, dans une bicoque prêtée par le père Forest, qu'il peint le portrait de Suzanne Valadon en 1885. Théophile-Alexandre Steinlen — peintre, affichiste et anarchiste suisse naturalisé — s'établit au n° 58 en 1883, puis reprend le propre atelier de Lautrec au n° 21 ; il mourra en 1923 dans un pavillon récupéré de l'Exposition universelle de 1900, au n° 73, où Auguste Renoir avait lui-même travaillé entre 1902 et 1903. Georges Seurat et Paul Signac gravitent dans le quartier ; en 1884 naît au n° 61 la Société des artistes indépendants, fondée en réaction contre le Salon officiel. Au n° 1, l'Hippodrome — inauguré entre 1900 et 1910 par une société à capitaux anglais — se transforme en 1911 en cinéma Gaumont Palace, colossal vaisseau de 5 000 places qui durera jusqu'en 1973.
Marcel Carné vit et travaille au n° 55 de 1935 à 1955 ; il fait du n° 21 le théâtre de son film L'assassin habite au 21 (1942). Marcel Aymé et Louis-Ferdinand Céline comptent parmi les plumes du quartier. Au bistrot Le Rêve (n° 89), Georges Simenon rédige son Roman d'une dactylo en 1924, et Jacques Brel, brisé par une rupture amoureuse, y écrit en 1958 les premiers vers de Ne me quitte pas. Durant l'Occupation, la rue est aussi le théâtre de réseaux : au n° 77 se tient une réunion scellant l'accord entre deux organisations de résistance, tandis qu'au n° 25 opère un réseau de renseignement communiste en lien avec Londres.