La rue du Mont-Cenis est l'une des artères les plus anciennes de la Butte — et l'une des plus physiques : ses 1 300 mètres de longueur dévalent la colline avec une brutalité toute alpine, ce qui lui a valu, lors de sa dénomination par arrêté du 20 juillet 1868, d'emprunter le nom du massif alpin du Mont-Cenis. Avant cela, la voie s'appelait — du moins dans sa partie basse, entre la rue Marcadet et les anciennes fortifications — chemin de la Procession, rappelant que les moines de Saint-Denis l'empruntaient lors de leur procession septennale. Rochegude signale qu'une section plus haute portait les noms de « chaussée Saint-Denis » puis « rue Saint-Denis », témoignant du rôle de cet axe comme voie de liaison entre l'abbaye royale et le sommet de la Butte.
Au n° 2, l'histoire s'étale sur vingt siècles. À l'emplacement de l'église Saint-Pierre de Montmartre — la plus vieille église de Paris encore debout, construite entre 1133 et 1147 sous Louis VI le Gros et consacrée par le pape Eugène III — on a retrouvé les traces d'un temple de Mars gallo-romain dont deux colonnes sont restées incorporées dans la façade méridionale. Sous les dalles du petit cimetière du Calvaire attenant repose entre autres Jean-Baptiste Pigalle, et c'est là aussi que fut inhumé Louis Antoine de Bougainville, premier Français à avoir bouclé le tour du monde. En 1590, Henri IV y pointe ses canons sur Paris assiégé ; en 1794, la Révolution transforme le sanctuaire en temple de la Raison, puis la Commune en fait un atelier de confection militaire où travaillent une cinquantaine de femmes — avant qu'il ne serve de dépôt de munitions. C'est également depuis la butte que Claude Chappe réalise en 1794 la première transmission télégraphique Paris-Lille via ses seize stations relais.
La rue fut aussi un repaire d'artistes et de bohèmes. Au n° 18, une maison disparue en 1925 — aujourd'hui commémorée par un bas-relief — fut dès 1823 le rendez-vous de nombreux peintres, et Kees van Dongen y aurait logé à son arrivée à Paris en 1897. Hector Berlioz habite au n° 24 entre 1834 et 1836, le temps de composer ses grandes fresques orchestrales. Au carrefour des n° 1-3 s'installe le cabaret La Bohème, haut lieu de la vie montmartroise que fréquentent Suzanne Valadon, le sculpteur Henri Laurens et bien d'autres ; le restaurant Le Moulin Joyeux (n° 5) voit défiler Valadon et son fils Maurice Utrillo entre 1919 et 1935. En 1922, c'est au n° 13 que le peintre Luc Lafnet héberge le jeune Georges Simenon à son arrivée à Paris. Plus tard, Patachou y tient sa pâtisserie-cabaret au n° 15 bis, où Georges Brassens et Jacques Brel font leurs premières armes. La rue garde aussi une curiosité géographique discrète : le point le plus élevé du sol naturel de Paris se trouve à l'intérieur du cimetière du Calvaire, au n° 2.