BACKGROUND: Separately addressing specific groups of people who share patterns of behavioral change might increase the impact of behavioral interventions to prevent transmission of sexually transmitted infections. We propose a method based on machine learning to assist the identification of such groups among men who have sex with men (MSM). METHODS: By means of unsupervised learning, we inferred "behavioral clusters" based on the recognition of similarities and differences in longitudinal patterns of condomless anal intercourse with nonsteady partners (nsCAI) in the HIV Cohort Study over the last 18 years. We then used supervised learning to investigate whether sociodemographic variables could predict cluster membership. RESULTS: We identified 4 behavioral clusters. The largest behavioral cluster (cluster 1) contained 53% of the study population and displayed the most stable behavior. Cluster 3 (17% of the study population) displayed consistently increasing nsCAI. Sociodemographic variables were predictive for both of these clusters. The other 2 clusters displayed more drastic changes: nsCAI frequency in cluster 2 (20% of the study population) was initially similar to that in cluster 3 but accelerated in 2010. Cluster 4 (10% of the study population) had significantly lower estimates of nsCAI than all other clusters until 2017, when it increased drastically, reaching 85% by the end of the study period. CONCLUSIONS: We identified highly dissimilar behavioral patterns across behavioral clusters, including drastic, atypical changes. The patterns suggest that the overall increase in the frequency of nsCAI is largely attributable to 2 clusters, accounting for a third of the population.