During the surveying of indigenous bacterial diversity in Taklimakan Desert of Xinjiang of China, we obtained 10 isolates, which possess a capacity to grow on 0.1×Tryptic Soy Broth agar supplemented with 1000 mg/L ampicillin. These bacteria display extensive resistances to different β-lactam antibiotics. All of these isolates belong to Proteobacteria. Five of them were identified as the human opportunistic pathogen Stenotrophomonas matltophila. Four strains were closely related to Mesorhizobium amorphae. It is interesting to see that one isolate A-3-E^T showed low 16S rRNA gene sequence similarity (< 96.8%) to those of the recognized species. The results of polyphasic taxonomy showed the strain represents a novel species of the new genus, for which the name Paramesorhizobium desertii gen. nov., sp. nov. is proposed. Moreover, it was found that high concentrations of β-lactam antibiotics are not able to inhibit the growth of strain A-3-E^T. The novel bacterium grows well in the media containing 1000 mg/L of cefazolin or 250 mg/L of cefotaxime. The strain also resists 17 of the 28 tested antibiotics. We just presented a case that the Taklimakan Desert is a natural reservoir of novel β-Lactam antibiotic resistant bacteria.