Compared with lean humans, the gut microbiota is altered in the obese. Whether these changes are due to an obesogenic diet, and whether the microbiota contributes to adiposity is currently discussed. In the cat population, where obesity is also prevalent, gut microbiome changes associated with obesity have not been studied. Consequently, the aim of this study was to compare the gut microbiota of lean cats, with that of overweight and obese cats. Seventy-seven rescue-shelter cats housed for ≥3 consecutive days were included in the study. Faecal samples were obtained by rectal swab and, when available, by a paired litter box sample. Body condition was assessed using a 9-point scoring system. DNA was extracted, and the 16S rRNA gene was amplified with a high-throughput quantitative real-time PCR chip. Overweight and obese cats had a significantly different gut microbiota compared to lean cats (p < 0.05), but this finding could not be linked to differences in specific bacterial groups. The rectal samples obtained higher DNA concentration than litter box samples (p < 0.0001). In conclusion, overweight and obese cats seem to have an altered gut microbiome as compared to lean cats.