L'origine du bâtiment est bien documentée. Par un acte du 25 novembre 1724, on sait que vient de débuter la construction d'un palais au sein de la Vila Nova, dont le commanditaire est le major Clément Guigliotti, de la famille de Lascaris des Ferres. En 1742, on apprend, grâce à une lettre, que le bâtiment n'est pas achevé, la hauteur des murs étant arrêtée à six mètres. Cette lettre mentionne aussi le nom de l'architecte "abbé Don Filippo", qui renverrait au grand architecte turinois Filippo Juvarra (sans certitude). Le palais est achevé vers 1768 par Clément Corvesi (ou Corvésy) di Gorbio, la branche des Guigliotti ayant été rattachée par mariage à celle des Corvesi. Clément Corvesi (1730-1796) a travaillé à la chancellerie de Sardaigne, a été avocat fiscal général puis 1er président du Sénat de Nice. Ce sont ses initiales qui ornent l'imposte de la porte d'entrée (CCG) avec la couronne comtale. On sait qu'en 1784 le rez-de-chaussée et le jardin sont loués à Joseph Peyre de Châteauneuf. Le palais est confisqué aux Corvesi après l'arrivée des troupes françaises et le receveur du district Defly, l'acquiert en 1794.

On ne sait pas à partir de quelle date le palais Corvesi accueille une fonction hôtelière, ni si à son ouverture vers 1810 l'Albergo dei Forestieri (puis Hôtel des Etrangers) est alors seulement localisé dans le palais ou s'il comprend déjà plusieurs bâtiments. Le palais est en tout cas lié, pendant tout le 19e siècle, à cet établissement hôtelier de grande renommée même si l'entrée principale est localisée au niveau d'autres bâtiments contigus, plus à l'ouest et que le palais Corvesi doit être vu plutôt, par la suite, comme un bâtiment annexe. Les témoignages différent d'ailleurs sur le nombre d'étages dévolus à l'hôtel en son sein. Son jardin forme en tout cas la pièce-maîtresse des espaces d'agrément extérieurs de l'hôtel. Un article de L'Eclaireur du dimanche (n°166, janvier 1924) reprend en partie la description qu'on en faisait à la fin du 18e siècle : "à la maison du président attenait un magnifique jardin, où les Niçois admiraient 97 arbres d'aigrure [agrumes], comme on disait, orangers, bigaradiers, citronniers, limoniers, tant gros que petits et une curiosité exceptionnelle pour notre pays, un coka du Pérou, l'arbuste dont les feuilles donnent l'alcaloïde [...]. Le jardin actuel de la cour intérieure de l'Hôtel des Etrangers comprend donc ce que fut le paradou du président du sénat [Clément Corvesi]". C'est la présence de ce jardin au sud (côté actuelle rue Alexandre-Mari) et à l'ouest, alors en coeur d'îlot, et où l'on trouve quatre gros mûriers, trois figuiers, une treille, un puits et un petit réservoir, qui fait la réputation de l'hôtel. Ce dernier supplante d'ailleurs son voisin l'Hôtel d'York qui ne bénéficie pas d'espaces extérieurs. Au 19e le palais est la propriété de la famille Alziari Héraud de Malaussena, qui le loue donc pour la partie hôtelière. Il est sans doute surélevé durant cette époque.

Le Palais Corvesi est le seul des nombreux bâtiments de l'hôtel à ne pas être démoli en 1936 lorsque la mairie rachète l'ensemble pour édifier un marché couvert. Il est transformé en bâtiment annexe de l'hôtel de ville proche. Une rénovation des décors intérieurs a lieu en 2009 (plaque dans la salle Lubonis du 1er étage) ainsi qu'un ravalement de façade avec application de décor en trompe l'oeil en 2010.