Late- and advanced HIV diagnoses remain significant challenges worldwide. Understanding the factors associated with and testing practice among those with late (CD4 < 350 cells/µL) and advanced diagnoses (CD4 < 200 cells/µL) is essential to diminish AIDS-related morbidity and mortality. This retrospective study manually reviewed e-medical records of new HIV diagnoses between 2011 and 2022 at Melbourne Sexual Health Centre, Australia. Among 606 new diagnoses, 25% (152/606) were late, 11% (65/606) were advanced, and 94% (568/606) were men who have sex with men. Among 352 overseas-born individuals, late or advanced diagnoses increased from 22% (4/18) in 2011 to 56% (5/9) in 2022. No significant change was observed among Australian-born individuals. Late diagnoses were associated with being born in Latin America or in East Asia and Pacific, having no prior sexually transmitted infection (STI) diagnosis in their lifetime, and no drug use in their lifetime. Advanced diagnoses were associated with being born in East Asia and the Pacific, having no prior STI, older age, Medicare-ineligibility, and unknown condom use history in the last year. Key barriers to earlier testing included LGBT-related stigma (n = 41) and recent arrival (< 5 years) in Australia (n = 41). The primary risk for contracting HIV was condomless anal sex (n = 80). To conclude, one in three new HIV diagnoses was late or advanced, with increased risk among overseas-born, Medicare-ineligible or those with perceived low risk. Tailored campaigns for these underserved populations are urgently needed to promote timely HIV testing.