La "rue du Clos Saint-Geneys" ou encore "la rue ou grand chemin de la porte de la Bout à la tour du Chastelain", inscrites dans les terriers du 16e siècle, seraient les noms d'une grande partie nord de l'actuelle rue du Palais. Cette voie longeait sur le côté ouest, l'ancien cimetière (actuelle place du Palais) et l'église Saint-Genès. C'est aussi l'une des premières voies de la ville haute, puisqu'elle était tracée à l'intérieur de la première enceinte du château et menait aux portes de ville, la porte de la Tour carrée au nord-ouest et la porte de la Bout à l'ouest. Dans cette partie nord, elle a fait l'objet de travaux de nivellement au cours du 15e siècle : à partir de 1474, des arasements sont effectués autour du château pour limiter la pente, ce qui entraîne le creusement d'une partie du chemin ; un mur de soutènement d'environ 2,30 m à 2,60 m de haut est alors construit pour contenir le terrain du cimetière (l'actuelle place) qui se retrouve en contrehaut. Dans sa partie sud, la rue du Palais se prolonge jusqu'à la rue Mancel-Chabot. Elle y descend, de nos jours, par l'intermédiaire d'escaliers qui ont vraisemblablement repris et remplacé l'ancien tracé du chemin à une époque indéterminée : ce tronçon aurait porté le nom de "rue de la Grole" ou " rue des Groslières" parce qu'il traversait le quartier "des Groslières" qui a ensuite donné son nom à l'actuelle rue Mancel-Chabot. Encore plus au sud, il est possible que la rue se soit prolongée directement selon le tracé de l'actuelle rue d'Alger.