A fundamental concept in evolutionary biology is that life tends to become more complex through geologic time, but empirical examples of this phenomenon are controversial. One debate is whether increasing complexity is the result of random variations, or if there are evolutionary processes which actively drive its acquisition, and if these processes act uniformly across clades. The mammalian vertebral column provides an opportunity to test these hypotheses because it is composed of serially-repeating vertebrae for which complexity can be readily measured. Here we test seven competing hypotheses for the evolution of vertebral complexity by incorporating fossil data from the mammal stem lineage into evolutionary models. Based on these data, we reject Brownian motion (a random walk) and uniform increasing trends in favor of stepwise shifts for explaining increasing complexity. We hypothesize that increased aerobic capacity in non-mammalian cynodonts may have provided impetus for increasing vertebral complexity in mammals.