Background: Incarcerated people are at a disproportionate risk of contracting HIV. We estimated the prevalence and correlates of HIV testing among incarcerated people with a history of HIV-related high-risk behaviours in Iran. Methods: Data for this analysis were obtained from three consecutive nationwide bio-behavioural surveillance surveys of a random sample of incarcerated people in 2009 (n = 5953), 2013 (n = 5490), and 2017 (n = 5785). History of testing for HIV in the last 12 months was the primary outcome variable. HIV testing was examined among those with a history of HIV-related high-risk behaviours (i.e., having multiple sex partnerships, injection drug use practices, or a history of having a tattoo). The outcome variable was divided into three categories: Never tested for HIV, ever tested for HIV inside the prison in the last 12 months, and ever tested for HIV outside the prison in the last 12 months. We used multivariable multinomial logistic regression models to examine factors associated with HIV testing. Results: Overall, 8,553 participants with a history of HIV-related high-risk behaviors with valid responses to the HIV testing question were included in the analysis. Although HIV testing inside prison has increased (23% [2009], 21.5% [2013], and 50.3% [2017]: P-value < 0.001), the prevalence of HIV testing outside prison has decreased (7.7% [2009], 7.5% [2013], 4.1% [2017]: P-value < 0.001) over time. Our multivariable multinomial regression model showed older age (Relative-risk ratio [RRR]: 1.24, 95% Confidence Intervals [CI]: 1.05, 1.47), history of the previous incarceration (RRR: 1.46, 95% CI: 1.24, 1.71), currently receiving methadone maintenance therapy inside prison (RRR: 2.09, 95% CI: 1.81, 2.43), having access to condoms inside prison (RRR: 1.42, 95% CI: 1.20, 1.68) and sufficient HIV knowledge (RRR: 1.74, 95% CI: 1.47, 2.05) were significantly associated with an increased probability of having an HIV test in the last 12 months inside prison. Conclusion: HIV testing among high-risk Iranian prisoners has increased from 2009 to 2017. However, HIV testing remains considerably low, and half of the incarcerated people with a history of HIV-related high-risk behaviours had never tested for HIV inside prison. Evidence-based programs are needed to optimize HIV testing inside and outside prisons and identify those at greater risk of HIV.