Due to globally increasing problems concerning biodeterioration of paints, it is worthwhile to enhance the determination of colony forming units (CFU) as a gold standard method via more rapid and culture-independent techniques. Here, we combined traditional culture-dependent techniques with subsequent sequencing, quantitative qPCR, and a serial quantification method (most probable number; MPN) to detect paint degrading bacteria in general and sulfate-reducing bacteria (SRB) in particular. During our investigation of three water-based paints that showed visible contamination, we found high bacterial counts of up to 107 CFU mL−1. Subsequent sequencing allowed the identification of common paint degraders including Bacillus sp. and Pseudomonas sp., but less frequently detected bacteria such as Rhodococcus sp. and Delftia spp. were also found to be present. MPN, as well as dsrA-targeted qPCR to detect SRB, only showed positive results for two out of three samples. These results coincided with the inherent physicochemical properties of the paints offering suitable conditions for microbial growth or not. The MPN method can be used for a diversity of aerobic and anaerobic bacteria and is rapid and reproducible. A combination of culture-independent techniques such as qPCR or NGS can help to fully elucidate the bacterial diversity in spoiled paint by also recovering anaerobic and unculturable ones.