Background/Objectives: Global population aging is associated with a rising prevalence of malnutrition among adults aged ≥80 years. Gut dysbiosis is linked to immune decline and impaired nutrient absorption, and aerobic exercise may enhance microbial diversity. This study investigated gut microbiota changes after a 12-week aerobic exercise intervention in octogenarians stratified by nutritional status. Methods: A total of 129 nursing home residents (≥80 years) were classified via the Mini Nutritional Assessment Short-Form (MNA-SF) into a healthy group (HG, MNA-SF ≥ 11) and a malnourished group (MG, MNA-SF < 11). Both groups underwent a 12-week brisk walking intervention (three sessions/week, 1 h/session, 40–60% heart rate reserve). Fecal samples were collected at baseline and post-intervention and were analyzed via shotgun metagenomic sequencing. Results: A total of 36 participants completed the intervention (HG = 17, MG = 19). Within-group baseline-to-post-intervention analysis showed no significant changes in alpha or beta diversity in the MG. However, post-intervention between-group comparison revealed higher microbial richness and diversity in the MG vs. the HG, with enrichment of taxa including Faecalibacterium prausnitzii and Streptococcus salivarius. Functional analysis revealed significant enhancements in metabolic pathways related to amino acid biosynthesis, protein synthesis, and quorum sensing in the MG. In contrast, the HG showed limited shifts in microbial diversity but an increase in species involved in carbohydrate metabolism. Conclusions: After 12 weeks, the malnourished group showed higher post-intervention microbial richness and diversity than the healthy group, with differences in taxonomic and predicted functional profiles. Without a non-intervention control group, the microbiota differences observed during the 12-week aerobic exercise period can only be considered observational associations, not causal. Additionally, the high dropout rate (72.1%) limits the generalizability of the findings. Clinical trial registration: The Chinese Clinical Trial Registry on 19 October 2022 (ChiCTR2200064801).