Although antiviral agents which block human immunodeficiency virus (HIV) replication can result in long-term suppression of viral loads to undetectable levels in plasma, long-term therapy fails to eradicate virus, which generally rebounds after a single treatment interruption. Multiple structured treatment interruptions (STIs) have been suggested as a possible strategy that may boost HIV-specific immune responses and control viral replication. We analyze viral dynamics during four, consecutive STI cycles in 12 chronically infected patients with a history (>2 years) of viral suppression under highly active antiretroviral therapy. We fitted a simple model of viral rebound to the viral load data from each patient by using a novel statistical approach that allows us to overcome problems of estimating viral dynamics parameters when there are many viral load measurements below the limit of detection. There is an approximate halving of the average viral growth rate between the first and fourth STI cycles, yet the average time between treatment interruption and detection of viral loads in the plasma is approximately the same in the first and fourth interruptions. We hypothesize that reseeding of viral reservoirs during treatment interruptions can account for this discrepancy, although factors such as stochastic effects and the strength of HIV-specific immune responses may also affect the time to viral rebound. We also demonstrate spontaneous drops in viral load in later STIs, which reflect fluctuations in the rates of viral production and/or clearance that may be caused by a complex interaction between virus and target cells and/or immune responses.