In this study, we assessed if the superimposition of incident sexually transmitted infections (STIs) on HIV phylogenetic analyses could reveal possible sexual behaviour misclassifications in our HIV-infected population. HIV-1 sequences collected between 1997 and 2014 from 1169 individuals attending a HIV clinic in Antwerp, Belgium were analysed to infer a partial HIV transmission network. Individual demographic, clinical and laboratory data collected during routine HIV follow-up were used to compare clustered and non-clustered individuals using logistic regression analyses. In total, 438 (37.5%) individuals were identified in 136 clusters, including 76 transmission pairs and 60 clusters consisting of three or more individuals. Individuals in a cluster were more likely to have a history of syphilis, Chlamydia and/or gonorrhoea (P < 0.05); however, when analyses were stratified by HIV transmission risk groups (heterosexual and men who have sex with men [MSM]), this association only remained significant for heterosexuals with syphilis (P = 0.001). Under closer scrutiny, this association was driven by six heterosexual men who were located in six almost exclusively MSM clusters. A parsimonious conclusion is that these six individuals were potentially misclassified as heterosexual. Improving the accuracy of sexual behaviour reporting could improve care.