In the present study, the purpose is to compare the effect of water extraction and alkali-assisted extraction on the structural characteristics and immunomodulatory activity of polysaccharides from Fuzhuan brick tea (FBTPs). The results indicated that water-extracted FBTPs (W-FBTPs) and alkali-extracted FBTPs (A-FBTPs) had similar molecular weights but different monosaccharide compositions, of which A-FBTPs had a higher yield and uronic acid groups corresponding to galacturonic acid (GalA). Moreover, A-FBTPs had stronger ability to promote phagocytic capacity, acid phosphatase activity and nitric oxide (NO) secretion in macrophages in vitro. In the in vivo study, A-FBTPs exhibited a promising effect to adjust the immune imbalance by enhancing the body features, antioxidant activities, immune response and intestinal mucosal barrier in cytoxan (CTX)-induced immunosuppressive mice. Besides, A-FBTP supplementation effectively improved CTX-induced gut microbiota dysbiosis, including promoting the abundance of beneficial bacteria (e.g., Lactobacillus) and short chain fatty acid (SCFA)-producing bacteria (e.g., Lachnospiraceae, Prevotellaceae and Ruminococcaceae), along with reducing the growth of potentially pathogenic microbes (e.g., Desulfovibrionaceae and Helicobacter). These findings suggested that alkaline extraction might be a promising way to obtain high-quality acidic polysaccharides from Fuzhuan brick tea (FBT), and A-FBTPs could be developed as novel potential prebiotics and immunomodulators for further application in food formulations.