Colorectal epithelial tumors occur spontaneously in dogs, and the pathogenesis seems to parallel that of humans. The development of human colorectal tumorigenesis has been linked to alterations in the composition of the intestinal microbiota. This study characterized the fecal- and mucosa-associated microbiota in dogs with colorectal epithelial tumors (n = 10). The fecal microbiota was characterized by 16S rDNA analysis and compared with that of control dogs (n = 13). We also determined the mucosa-associated microbiota composition in colonic tumor tissue (n = 8) and in adjacent non-tumor tissue (n = 5) by 16S rDNA- and rRNA profiling. The fecal microbial community structure in dogs with tumors was different from that of control samples and was distinguished by oligotypes affiliated with Enterobacteriaceae, Bacteroides, Helicobacter, Porphyromonas, Peptostreptococcus and Streptococcus, and lower abundance of Ruminococcaceae, Slackia, Clostridium XI and Faecalibacterium. The overall community structure and populations of mucosal bacteria were not different based on either the 16S rDNA or the 16S rRNA profile in tumor tissue vs. adjacent non-tumor tissue. However, the proportion of live, potentially active bacteria appeared to be higher in non-tumor tissue compared with tumor tissue and included Slackia, Roseburia, unclass. Ruminococcaeceae, unclass. Lachnospiraceae and Oscillibacter. Colorectal tumors are rarely diagnosed in dogs, but despite this limitation, we were able to show that dogs with colorectal tumors have distinct fecal microbiota profiles. These initial results support the need for future case-control studies that are adequately powered, as well as age-matched and breed-matched, in order to evaluate the influence of bacteria on colorectal cancer etiopathogenesis and to determine whether the bacteria may have potential as biomarkers in clinical settings.