Un día, Ferdinand Cheval tropezó con una piedra cuya singular forma le fascinó. Luego se dio cuenta de que muchas otras piedras similares cubrían el suelo allí. Inspirado, se le ocurrió la idea del Palacio, y luego recolectó y seleccionó estas piedras durante meses para integrarlas a la estructura. La primera piedra se llama "piedra de tropiezo" y es visible en una de las fachadas del Palacio.