Disease progression models are useful tools for gaining a systems' understanding of the transitions to disease states, and characterizing the relationship between disease progress and factors affecting it such as patients' profile, treatment and the HIV diagnosis stage. Patients are classified into four states (based on CD4+ T-lymphocyte count) and all the transitions are allowed. Examinations to identify disease progression of the patient are carried out routinely throughout the follow-up period. Therefore, the times spent at the various HIV infection stages are interval censored or right censored. This makes difficult to use simple statistical methods such as regression to model the disease progression and its relationship with the diagnosis stage. We present a novel, more intuitive and realistic approach based on phase type distributions to model progression of HIV infection and the effects and prognostic significance of HIV diagnosis stage. The approach is illustrated using a real database of total 2,092 HIV infected patients enrolled in the Italian public structures from January 1996 to January 2008. The approach can also be used to examine the effect of other covariates such as patient's profile.