Ultra-processed foods (UPFs) consumption could affect gut microbiota diversity and profile. We aimed to evaluate the effects of UPFs on microbiota, considering the role of sex. The consumption of UPFs (using NOVA criteria) was assessed with a validated 137-item food-frequency questionnaire. Participants (n = 359) were classified into less than three servings per day (n = 96) of UPFs and more than five (n = 90). Women and men were subclassified following the same criteria. 16S rRNA sequencing was performed from DNA fecal samples, and differences in microbiota were analyzed using EdgeR. The relationship between UPFs and bacteria was assessed by Spearman correlation and comparison of tertiles of consumption. Women who consumed more than five servings/day of UPFs presented an increase in Acidaminococcus, Butyrivibrio, Gemmiger, Shigella, Anaerofilum, Parabacteroides, Bifidobacterium, Enterobacteriales, Bifidobacteriales and Actinobacteria and a decrease in Melainabacter and Lachnospira. Bifidobacterium, Bifidobacteriales and Actinobacteria was positively associated with pizza and Actinobacteria with industrially processed dairy in women. Men who consumed more than five servings/day presented an increase of Granulicatella, Blautia, Carnobacteriaceae, Bacteroidaceae, Peptostreptococcaceae, Bacteroidia and Bacteroidetes and a decrease of Anaerostipes and Clostridiaceae. Bacteroidia and Bacteroidetes correlated positively with industrially processed meat. This study suggests that UPFs may affect microbiota composition differently in women and men.