Cette voie doit son nom au palais de l'Intendant, aménagé en 1688 dans l'ancienne brasserie de Jean Talon, au pied de la côte. À partir de 1663, l'intendant est le deuxième personnage le plus important de la Nouvelle-France, après le gouverneur. Le palais est non seulement son lieu de résidence, mais c'est là qu'il préside les réunions du Conseil souverain, c'est là que se trouvent la cour de justice et la prison. Ce premier palais en bois est détruit par un incendie en 1713. Trois ans plus tard, on élève sur les ruines du bâtiment les « magasins du roi » constitués principalement d'un vaste entrepôt de marchandises et de munitions pour la colonie. On érige aussi un deuxième palais au nord du précédent, dont subsistent encore aujourd'hui les voûtes. L'imposant édifice en pierre est entouré des écuries, des magasins du roi, d'entrepôts et d'autres dépendances. Rasé lui aussi par un incendie en 1725, le second palais est immédiatement reconstruit. À partir de la Conquête, le palais est occupé un temps par les troupes britanniques qui l'incendient volontairement en 1775, le lieu ayant été investi par les troupes américaines de Benedict Arnold.

Anciens toponymes
Cette côte, ouverte en 1714, portait le nom de rue du Palais à la basse-ville et de rue des Pauvres à la haute-ville. La rue des Pauvres descendait de la rue Saint-Jean à l'ancienne porte du Palais disparue en 1873. Elle traversait le « domaine des pauvres de l'Hôtel-Dieu », appelé ainsi parce que les revenus qu'il générait étaient affectés aux démunis de l'Hôtel-Dieu. Le 19 décembre 1890, les rues du Palais et des Pauvres ont été réunies sous le nom de côte du Palais.