We calculate the band structure of ultracold atoms located inside a laser-driven optical cavity. For parameters where the atom-cavity system exhibits bistability, the atomic band structure develops loop structures akin to the ones predicted for Bose-Einstein condensates in ordinary (noncavity) optical lattices. However, in our case the nonlinearity derives from the cavity back-action rather than from direct interatomic interactions. We find both bi- and tristable regimes associated with the lowest band, and show that the multistability we observe can be analyzed in terms of swallowtail catastrophes. Dynamic and energetic stability of the mean-field solutions is also discussed, and we show that the bistable solutions have, as expected, one unstable and two stable branches. The presence of loops in the atomic band structure has important implications for proposals concerning Bloch oscillations of atoms inside optical cavities [Peden et al., Phys. Rev. A 80, 043803 (2009); Prasanna Venkatesh et al., Phys. Rev. A 80, 063834 (2009)].