An application of semi-Markov models to AIDS disease progression was utilized to find best sojourn time distributions. We obtained data on 370 HIV/AIDS patients who were under follow-up from September 2008 to August 2015, from Yirgalim General Hospital, Ethiopia. The study reveals that within the “good” states, the transition probability of moving from a given state to the next worst state has a parabolic pattern that increases with time until it reaches a maximum and then declines over time. Compared with the case of exponential distribution, the conditional probability of remaining in a good state before moving to the next good state grows faster at the beginning, peaks, and then declines faster for a long period. The probability of remaining in the same good disease state declines over time, though maintaining higher values for healthier states. Moreover, the Weibull distribution under the semi-Markov model leads to dynamic probabilities with a higher rate of decline and smaller deviations. In this study, we found that the Weibull distribution is flexible in modeling and preferable for use as a waiting time distribution for monitoring HIV/AIDS disease progression.