We modeled the decline of CD4+ T-lymphocytes (T4 cells) in HIV-infected individuals with a continuous-time Markov process. The model partitions the HIV infection period into six progressive T4-cell count intervals (states), followed by a seventh state: a definitive HIV-infection end point, i.e., AIDS diagnosis or Walter Reed stage 6 (opportunistic infections). The Markov model was used to estimate the state-specific progression rates from data as functions of important progression cofactors. We applied the model to data on 1,796 HIV-positive individuals in the U.S. Army. The estimated mean waiting time from seroconversion to when the T4-cell count persistently drops below 500/mm3, but is greater than 349/mm3, is 4.1 years, and the waiting time to a T4-cell count of less than 200/mm3 is estimated at 8.0 years. The estimated rate of T4-cell decline was higher for HIV-infected individuals with initially high numbers of T4 cells, but the estimated rate of decline remains relatively uniform when the T4-cell count dropped persistently below 500/mm3. The opportunistic infection incubation period, i.e., the time from seroconversion to opportunistic infection diagnosis, is estimated at 9.6 years. Age is found to be an important cofactor. The estimated mean opportunistic infection incubation periods are 11.1, 10.0, and 8.9 years for the youngest (≤ 25 years old), the middle (26–30 years old), and the oldest (> 30 years old) age groups, respectively. Moreover, we found that the rate of progression is the same for all three age groups when T4-cell counts are ≥ 500/mm3, but it is faster for the two older age groups when T4-cell are < 500/mm3.