Rapid rebound of plasma viremia in patients after interruption of long-term combination antiretroviral therapy (cART) suggests persistence of low-level replicating cells or rapid reactivation of latently infected cells. To further characterize rebounding virus, we performed extensive longitudinal clonal evolutionary studies of HIV env C2-V3-C3 regions and exploited the temporal relationships of rebounding plasma viruses with regard to pretreatment sequences in 20 chronically HIV-1-infected patients having undergone multiple 2-week structured treatment interruptions (STI). Rebounding virus during the short STI was homogeneous, suggesting mono- or oligoclonal origin during reactivation. No evidence for a temporal structure of rebounding virus in regard to pretreatment sequences was found. Furthermore, expansion of distinct lineages at different STI cycles emerged. Together, these findings imply stochastic reactivation of different clones from long-lived latently infected cells rather than expansion of viral populations replicating at low levels. After treatment was stopped, diversity increased steadily, but pretreatment diversity was, on average, achieved only >2.5 years after the start of STI when marked divergence from preexisting quasispecies also emerged. In summary, our results argue against persistence of ongoing low-level replication in patients on suppressive cART. Furthermore, a prolonged delay in restoration of pretreatment viral diversity after treatment interruption demonstrates a surprisingly sustained evolutionary bottleneck induced by punctuated antiretroviral therapy.