Solids with competing interactions often undergo complex phase transitions with a variety of long-periodic modulations. Among such transition, devils 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 Neel temperature. An evolution of the low-energy electronic structure going through the devils staircase is of special interest, which has, however, been elusive so far despite the 40-years of intense researches. Here we use bulk-sensitive angle-resolved photoemission spectroscopy and reveal the devils staircase transition of the electronic structures. The magnetic reconstruction dramatically alters the band dispersions at each transition. We moreover 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 devils staircase.