Solids with competing interactions often undergo complex phase transitions with a variety of long-periodic modulations. Among such transition, devil's staircase is the most complex phenomenon, and for it, CeSb is the most famous material, where a number of the distinct phases with long-periodic magnetostructures sequentially appear below the Néel temperature. An evolution of the low-energy electronic structure going through the devil's staircase is of special interest, which has, however, been elusive so far despite 40 years of intense research. Here, we use bulk-sensitive angle-resolved photoemission spectroscopy and reveal the devil's staircase transition of the electronic structures. The magnetic reconstruction dramatically alters the band dispersions at each transition. Moreover, we find that the well-defined band picture largely collapses around the Fermi energy under the long-periodic modulation of the transitional phase, while it recovers at the transition into the lowest-temperature ground state. Our data provide the first direct evidence for a significant reorganization of the electronic structures and spectral functions occurring during the devil's staircase.