Background The dog is the most popular companion animal and is a valuable large animal model for several human diseases. Canine immune-mediated hematological diseases, including immune-mediated hemolytic anemia (IMHA) and immune thrombocytopenia (ITP), share many features in common with autoimmune hematological diseases of humans. The gut microbiome has been linked to systemic illness, but few studies have evaluated its association with immune-mediated hematological disease. To address this knowledge gap, 16S rRNA gene sequencing was used to profile the fecal microbiota of dogs with spontaneous IMHA and ITP at presentation and following successful treatment. In total, 21 affected and 13 healthy control dogs were included in the study. Results IMHA/ITP is associated with remodeling of fecal microbiota, marked by decreased relative abundance of the spirochete Treponema spp., increased relative abundance of the pathobionts Clostridium septicum and Escherichia coli, and increased overall microbial diversity. Logistic regression analysis demonstrated that Treponema spp. were associated with decreased risk of IMHA/ITP (odds ratio [OR] 0.24–0.34), while Ruminococcaceae UCG-009 and Christensenellaceae R-7 group were associated with increased risk of disease (OR = 6.84 [95% CI 2–32.74] and 8.36 [95% CI 1.85–71.88] respectively). Conclusions This study demonstrates an association of immune-mediated hematological diseases in dogs with fecal dysbiosis, and points to specific bacterial genera as biomarkers of disease. Microbes identified as positive or negative risk factors for IMHA/ITP represent an area for future research as potential targets for new diagnostic assays and/or therapeutic applications.