Long-term exposure to combination antiretroviral therapy (cART) may be associated with accelerated ageing. Telomere length is considered to be reliable aging biomarker. The aim of this study was to compare patients’ relative telomere length (RTL) between and within different cART classes and to estimate the impact of certain HIV-related variables on RTL. The study was conducted in 176 HIV-infected male patients receiving cART, with ≤50 copies HIV RNA/mL plasma. RTL was determined from mononuclear cells by quantitative polymerase chain reaction. Standard statistical tests and unsupervised machine learning were performed. The mean RTL was 2.50 ± 1.87. There was no difference (p = 0.761) in RTL between therapeutic groups: two nucleoside reverse transcriptase inhibitors as the backbone treatment, combined with either integrase inhibitor, protease inhibitor, or non-nucleoside reverse transcriptase inhibitor (NNRTI). Machine learning results suggested duration of HIV infection, CD4+ T-cell count, and cART, including NNRTI, as potentially significant variables impacting RTL. Kendall’s correlation test excluded duration of HIV infection (p = 0.220) and CD4+ T-cell count (p = 0.536) as significant. The Mann–Whitney test confirmed that cART containing NNRTI impacted RTL (p = 0.018). This was the first study to show that patients using efavirenz within cART had significantly shorter telomeres than patients using nevirapine.