L'archevêque de Sens avait l'évêché de Paris dans sa circonscription de Quatrième Lyonnaise et possédait une résidence dans cette ville depuis 1292.
Au début du XIV? siècle, la monarchie gère la France en cohabitation avec l'église catholique, qui imprime sa lourde influence sur des territoires gérés par des archevêques. À cette époque, le Pape est représenté à Paris par Guillaume de Melun, puissant archevêque de Sens et conseiller personnel des rois de France.
Le jeune Charles V n'aime pas trop séjourner au Louvre, qui n'est à cette époque qu'un étroit et sinistre donjon. Il décide donc de se faire construire un nouvelle grande résidence royale, et acquiert en 1366 en ensemble d'habitations dans le quartier du Marais, qui comprend l'hôtel particulier de l'archevêque de Sens.
Une centaine d'années plus tard, le bâtiment revient au culte, qui décide d'y reloger le nouvel archevêque Sens depuis 1475, Tristan de Salazar. L'ecclésiastique s'affaire alors à transformer sa demeure en luxueux châtelet dans le style gothique flamboyant. Les magnifiques petits donjons, les voûtes de pierre, les escaliers et les fenêtres sont façonnés et décorés avec une grande finesse par les maçons, de sorte à ce que l'hôtel ressemble plus à un petit château qu'à une demeure religieuse, rappelant au passage la toute puissance du Vatican; cela en fait le plus beau des palais parisiens de cette époque.
Marguerite de Valois, dont le mariage avec Henri IV est déclaré nul en 1599 par l'Église, y réside quelques mois. Celle que l'on surnomme désormais "La Reine Margot" profite des entrées discrètes pour dévoiler ses charmes à un éphèbe de 18 ans. Malheureusement l'amourette est de courte durée puisque l'amant est assassiné juste devant l'édifice par son prédécesseur, lui aussi un autre jeune bellâtre âgé d'à peine 20 ans !
Paris est érigé en archevêché en 1622, et les archevêqies de Sens cessent d'utiliser l'hôtel et le louent.
De 1689 à 1743, il devient le siège des "Messageries, coches et carosses de Lyon, Bourgogne et Franche-Comté".
D'autres entreprises de roulage leur succèdent, puis une conserverie, une fabrique de confitures, une verrerie, etc.
La Ville de Paris rachète l'hôtel de Sens en 1911, et le fait restaurer pour y installer la bibliothèque Forney.