HIV/AIDS progression is inherently a multi-state stochastic process in which transitions among immunological states evolve over time and are influenced by therapeutic interventions. Standard homogeneous Markov models cannot adequately capture this temporal heterogeneity, necessitating more flexible stochastic frameworks. This study develops and evaluates a multi-state non-homogeneous semi-Markov model (MNHSMM) for characterizing HIV progression across six clinically defined immunological states and estimating state-specific sojourn-time distributions and transition probabilities as functions of calendar time and treatment status. Longitudinal data from 500 HIV-positive adults followed for a median of 84 months were analyzed. The proposed six-state MNHSMM incorporated Weibull-distributed sojourn times and time-varying transition kernels parameterized using B-spline functions, with parameters estimated through maximum likelihood estimation. Model performance was compared with that of homogeneous Markov and homogeneous semi-Markov models using the Akaike information criterion (AIC), Bayesian information criterion (BIC), and likelihood-ratio tests. The MNHSMM achieved the lowest AIC (3281.4) and BIC (3402.6) and significantly outperformed the homogeneous semi-Markov model, χ²(16) = 174.2, p < .001. The mean sojourn time in the asymptomatic state was 28.4 months (95% CI [25.1, 31.7]). Patients receiving antiretroviral therapy exhibited significantly longer sojourn times across all nonabsorbing states and a 37% lower probability of transitioning to death within five years. These findings establish the MNHSMM as a statistically superior and clinically informative framework for modeling HIV progression. Its temporal flexibility can improve long-term survival prediction, support the identification of optimal antiretroviral therapy intervention windows, and inform healthcare planning in sub-Saharan Africa and beyond.