Sexual behavior is heterogeneous and dynamic. Characterization of such complexity constitutes evidence for public health authorities and caregivers concerned with the framing of sexual health messages aimed at specific subgroups. We developed a machine-learning-based methodology for inference and characterization of such subgroups from longitudinal data on men who have sex with men (MSM) attending individual sexual health counseling sessions. Because longitudinal data take time to record, we assessed the ability of first visit data to predict subgroups' membership. Our methodology comprised two main steps: (1) Hierarchical clustering to group 2349 HIV-negative MSM based on their self-reported longitudinal sexual behavior during visits to Swiss sexual health counseling centers between November 2016 and April 2019; and (2) Random forest-based classification to predict subgroup membership from first visit data. We found six subgroups with significant differences in behavioral trends, most of which sharply deviated from the overall trends. Two subgroups, which contained 37% of the study population, accounted for over 70% of the overall increases in condomless anal intercourse with non-steady partners, group sex, and having more than five anal intercourse partners. Subgroup-specific trends in online-dating and group sex were heterogeneous with opposing trends across subgroups. Data from first visits predicted trends of sexual behavior with accuracy ranging from 64 to 86%. This study evidenced specific sexual behavioral subgroups that might benefit from customized sexual health messages, demonstrated that first visit registries could predict subgroups, and contributes an algorithmic alternative for establishing subgroups relevant to inform customized sexual health messages that capture sexual behavioral diversity.