The HIV epidemic is primarily characterised by the circulation of HIV-1 group M (main) comprising of 11 subtypes and sub-subtypes (A1, A2, B-D, F1, F2, G, H, J, and K) and to date 55 circulating recombinant forms (CRFs). In Southeast Asia, active inter-subtype recombination involving three main circulating genotypes--subtype B (including subtype B', the Thai variant of subtype B), CRF01_AE, and CRF33_01B--have contributed to the emergence of novel unique recombinant forms. In the present study, we conducted the molecular epidemiological surveillance of HIV-1 gag-RT genes among 258 people who inject drugs (PWIDs) in Kuala Lumpur, Malaysia, between 2009 and 2011 whereby a novel CRF candidate was recently identified. The near full-length genome sequences obtained from six epidemiologically unlinked individuals showed identical mosaic structures consisting of subtype B' and CRF01_AE, with six unique recombination breakpoints in the gag-RT, pol, and env regions. Among the high-risk population of PWIDs in Malaysia, which was predominantly infected by CRF33_01B (>70%), CRF58_01B circulated at a low but significant prevalence (2.3%, 6/258). Interestingly, the CRF58_01B shared two unique recombination breakpoints with other established CRFs in the region: CRF33_01B, CRF48_01B, and CRF53_01B in the gag gene, and CRF15_01B (from Thailand) in the env gene. Extended Bayesian Markov chain Monte Carlo sampling analysis showed that CRF58_01B and other recently discovered CRFs were most likely to have originated in Malaysia, and that the recent spread of recombinant lineages in the country had little influence from neighbouring countries. The isolation, genetic characterization, and evolutionary features of CRF58_01B among PWIDs in Malaysia signify the increasingly complex HIV-1 diversity in Southeast Asia that may hold an implication on disease treatment, control, and prevention.