The number of new HIV diagnoses is increasing in the western world and transmission clusters have been recently identified among men having sex with men despite Highly Active Antiretroviral Therapy efficacy. The objective of this study was to assess temporal trends, epidemiological, clinical and virological characteristics of primary HIV infections. A retrospective analysis of 79 patients presenting primary HIV infections from 2005 to 2012 was performed in Marseille University Hospitals, southeastern France. Clinical, epidemiological and immunovirological data including phylogeny based on the polymerase gene were collected. 65 males and 14 females were enrolled. The main transmission route was homosexual contact (60.8%). Patients were mostly infected with subtype B (73.4%) and CRF02_AG (21.5%) HIV-1 strains. An increase in the annual number of HIV seroconversions among new HIV diagnoses from 5% in 2005 to 11.2% in 2012 (P = 0.06) and of the proportion of CRF02_AG HIV strains among primary HIV infections in 2011-2012 as compared to 2005-2010 (P = 0.055) was observed. Phylogenetic analysis revealed four transmission clusters including three transmission clusters among men having sex with men: two large clusters of nine CRF02_AG, six B HIV strains; and one small cluster of three B HIV strains. Clusters involved more frequently men (P = 0.01) belonging to caucasian ethicity (P = 0.05), with a higher HIV RNA load at inclusion (P = 0.03). These data highlight the importance of improving epidemiological surveillance and of implementing suitable prevention strategies to control the spread of HIV transmission among men having sex with men.