Ferdinand Cheval tombe un jour sur une pierre dont la forme singulière le fascine. Il s'est alors rendu compte que de nombreuses autres pierres similaires jonchaient le sol à cet endroit. Inspiré, l'idée du Palais lui est venue, et il a alors collecté et sélectionné ces pierres pendant des mois pour les intégrer à la structure. La toute première pierre s'appelle la "pierre d'achoppement" et est visible sur l'une des façades du Palais.