This study examined the biodegradation of natural rubber (NR) and deproteinized natural rubber (DPNR) by bacterial consortia enriched from a rubber-processing factory’s waste in Vietnam. The results reveal the degradation in both NR and DPNR, and the DPNR was degraded easier than NR. The highest weight loss of 48.37% was obtained in the fourth enrichment consortium with DPNR, while 35.39% was obtained in the fifth enrichment consortium with NR after 14 days of incubation. Nitrogen content and fatty acid content determined by Kjeldahl method and fourier transform infrared spectroscopy (FTIR), respectively, were decreased significantly after being incubated with the consortia. Structure of degraded rubber film analyzed by nuclear magnetic resonance spectroscopy showed the presence of aldehyde group, a sign of rubber degradation. Bacterial cells tightly adhering and embedding into NR and DPNR films were observed by scanning electron microscopy. There were differences in the bacterial composition of the consortia with NR and DPNR, which were determined by metagenomic analysis using 16S rRNA gene sequencing. The phyla Bacteroidetes and Proteobacteria may play a role in the degradation of non-isoprene compounds such as protein or lipid, while the phylum Actinobacteria plays a crucial role in the degradation of rubber hydrocarbon in all consortia.