Sur le plan cadastral de 1812 existe un petit bâtiment sans doute rural, propriété de Joseph Fodon. Les terrains se rapportant à la maison sont mentionnés comme porteurs de vignes, oliviers, orangers et labours.

Une construction plus étendue, avec jardin au tracé régulier au nord, apparaît sur un plan de 1837 du secteur de la Croix-de-Marbre. Cela indique donc un changement de fonction du bâtiment, vers de l'agrément. Les extrémités du bâtiment représentés en teinte plus claire peuvent correspondre à des ailes plus basses. En 1853, le comte Alexandre Saissi de Châteauneuf vend pour 170 000 f la propriété à un certain Manatti. Sur le plan régulateur de 1855 apparaît comme propriétaire Mattirolo (ou Martirolo) ainsi que la femme Mannatti. La veuve Thérèse Mannatti vend pour 240 000 f moitié à Joseph Cassin et moitié à François Léon Lefebvre. Ces derniers revendent en 1869 au fils de Villaine pour 300 000 f. (acte notarié 2E15 257). En 1870, l'architecte Sébastien Marcel Biasini intervient une première fois pour le propriétaire Victor De Villaine qui envisage d'y installer un hôtel garni (Le Journal de Nice, 20 février 1870).

Sur le cadastre de 1873, apparaissent les deux avant-corps latéraux en demi-cercle encore présents de nos jours. Absents sur un plan-guide de la ville de 1865, on peut en déduire qu'ils sont la conséquence de l'intervention de S. M. Biasini en 1870. Le palais est habité à cette époque par l'archiduchesse Stéphanie de Bade et en 1877, l'exposition de peintures et sculptures de la Société des Beaux-Arts s'y déroule. Il est ensuite la propriété du général russe Schablikine.

Le plan pittoresque de 1878 montre que sa façade principale au sud correspond à celle encore visible de nos jours. L'édifice se nomme alors sur le plan Palais Marie-Christine mais il n'y a aucune preuve de la présence de l'épouse du roi Charles-Félix de Sardaigne en ses murs lors de son séjour à Nice en 1826.

En 1881 l'administration du Grand Cercle, qui a loué le palais pour douze années, mandate l'architecte Sébastien Marcel Biasini pour effectuer des transformations et créer l'escalier monumental. Pour l'édifier, il comble le "U" au nord, par un bâtiment rectangulaire. Il est aidé à cette occasion par un architecte de Paris mentionné "Charpentier". Le Grand Cercle fonctionne comme un casino et ses directeurs sont accusés de malversations, ce qui est dénoncé dans la presse nationale. En 1884, le palais est le siège d'un Cercle républicain.

En 1890 la famille Orlay de Carva (famille russe qui a un hôtel particulier à Paris au 93 boulevard Berthier) remplace le général Schablikine. Les deux toiles marouflées décoratives du peintre Nestor Fiocchi, sises dans l'escalier monumental, sont datées de cette année (signature et datation sur les toiles).

En 1891, un Institut médical cinésique est dans les murs. Une autre grande toile peinte se situe dans l'escalier monumental, signée de Napoléon Duitz et datée de 1910, sans que l'on en connaisse le commanditaire ni la raison de cet embellissement. Dans les années 1930, la Galerie Pompadour (décoration d'intérieurs) y est installée. A la fin des années 1930 l'Union coloniale indochinoise y a son siège.

En 2022, la porte vitrée du hall porte toujours l'inscription : Union coloniale et de la France d'Outremer. Le bâtiment accueille dans sa totalité des bureaux.