Background/Objectives: Sarcopenia (SA), an age-related impairment in skeletal muscle mass and function, is related to gut microbiota (GM) through inflammation and short-chain fatty acid (SCFA) generation. However, data on this relationship in older Japanese adults remain limited. We investigated the relationship of GM composition with SA, based on the Asian Working Group for Sarcopenia (AWGS) 2019 criteria, among elderly Japanese outpatients. Methods: Between June 2022 and January 2023, this prospective cross-sectional study enrolled 356 community-dwelling outpatients aged ≥ 65 years at the Department of Gastroenterology, Juntendo Tokyo Koto Geriatric Medical Center. SA was determined based on the AWGS 2019 consensus criteria. GM was analyzed using 16S rRNA gene sequencing, and alpha/beta diversity, taxonomic composition, detection rates, and correlations with skeletal muscle mass index (SMI), grip strength, and gait speed were investigated. Results: Among 356 (144 males, 212 females) participants, 50 (35 males, 15 females) had SA. Differences in GM diversity and composition were primarily noted among male participants. Men with SA had lower alpha diversity and distinct beta diversity profiles. Six bacterial genera—Eubacterium I, Fusicatenibacter, Holdemanella, Unclassified Lachnospira, Enterococcus H, and Bariatricus—had lower abundances in the SA group. Several of these genera showed positive correlations with SMI, grip strength, and gait speed. Conversely, no differences in GM characteristics were seen among females. Conclusions: GM composition was associated with SA among older Japanese men. These sex-specific differences emerged consistently, highlighting the potential of microbiota-based strategies for SA prevention in older males.