Un cartouche au-dessus de l'entrée du 1, rue Partouneaux porte la date 1909 et les initiales CRL correspondant à Carlotta (ou Charlotte) et Richard Leubner. Une demande de placement d’échafaudage par un entrepreneur en mai 1909 témoigne du fait que la construction est en cours en cette date. Les époux Leubner, de nationalité allemande, sont arrivés à Menton avec leurs enfants vers 1888 et Richard W. Leubner, né en 1855 à Hambourg , exploite l'hôtel Victoria et des Princes depuis 1889. Le nouvel hôtel apparait sous le nom de Grand Hôtel Leubner sur un plan de la ville et des publicités en 1913. Il compte alors 115 chambres et appartient à Madame Leubner, Richard Leubner étant décédé en décembre 1909 (sa tombe se trouve au cimetière du Vieux château). Les plans sont attribués à l'architecte mentonnais Alfred Auguste Marsang. Au soubassement, un four porte une plaque de fabriquant : H. AUTTIE constructeur 9 bd Charles III Monaco. Une carte postale antérieure à la guerre de 1914 montre l'hôtel portant l'appellation de Leubner's Hôtel. Pendant la guerre l'hôtel est transformé en hôpital militaire (hôpital Douine) de 260 lits. Comme tous les biens appartenant à des Allemands, il avait été mis sous séquestre.

Une publicité pour l'hôtel Majestic, en 1928, mentionne que l'hôtel appartient à l'hôtelier suisse Charles Bachler. Un rapport de l'architecte voyer de la ville du 16 mai 1929 fait état que le propriétaire du fond G. Martin demande l'autorisation d'aménager les combles en chambres du personnel et d'installer le tout-à-l'égout.

Le Majestic est très endommagé pendant la guerre, les deux étages de combles ayant été détruits par un obus. Il rouvre à la saison estivale 1949. Le toit brisé à lucarnes est remplacé par un toit terrasse sur lequel sont aménagées des chambres pour loger le personnel.

En 1956, l'hôtel est transformé en 50 appartements par l'architecte Ange Musante. Les élévations extérieures ont été peu modifiées. Le hall d'entrée principal qui se trouvait sur l'angle a été fermé. Il est occupé par une boulangerie qui a conservé des plafonds ornés de gypserie.