Characterization of HIV subtypes can provide a more comprehensive understanding of the epidemic within a distinct region, and when combined with notification data, may also be helpful in enhancing current HIV prevention strategies. In this study, we characterized 1056 HIV-positive individuals (948 males and 108 females) living in Victoria and whose infection was detected for the first time between 2005 and 2010 inclusive. HIV-1 strains were subtyped based on pol gene sequence. Phylogenetic analysis was performed on all non-B subtype sequences identified. Of the 1056 sequences analyzed, 825 were subtype B and 231 were non-B. Overall 6 HIV-1 subtypes, 6 circulating recombinant forms (CRFs), and 12 unique recombinant forms (URFs) were identified. Regardless of gender, the majority of individuals were infected with a subtype B virus (78%). Subtype B was dominant in males (n=806, 85%). In contrast, the majority of females were infected with non-B subtypes (n=89, 82%), in particular subtype C (n=48, 45%). Phylogenetic analysis of the non-B subtypes revealed that the majority of clustering, and thereby transmission, occurred with CRF01_AE strains. Despite the relatively high numbers identified in females there was very little clustering of subtype C viruses. Subtypes C and A1 both historically associated with heterosexual transmission, and CRF01_AE often associated with IVDU, were also associated with transmission within the MSM population, demonstrating the potential for non-B subtypes to expand into the MSM population. The observation of increasing numbers of females and heterosexual males infected with non-subtype B viruses, the majority imported through migration and travel to countries where there is a high prevalence of HIV, suggests a targeted public health message may be required to prevent further increases within these two groups.