Microbial bioremediation techniques continued to generate increasing interest due to its cost-effectiveness and being environmentally friendly. In the present study, Klebsiella variicola Wt, K. variicola MutAc and K.variicola MutEb were used to bioremediate Cd2+ and Pb2+ simulated contaminated soil in a pot experiment and their genetic variability were determined. The genetic variability among the Klebsiella variicola wild type and the mutant strains were investigated using 10 RAPD primers which revealed that 89.7% were polymorphic while 10.3% were monomorphic. The polymorphic information content (PIC) ranged from 0.52–0.86 while the diversity of the gene ranged from 0.56–0.88, this indicated an enormous heterozygosis associated with a high degree of polymorphism and diversity which make Klebsiella variicola mutant strains unique. The initial Cd2+ and Pb2+ in the simulated soil was 500 and 545 mg/Kg respectively while the Pb2+ concentration in the unsimulated soil was 45 mg/Kg. it was observed that K.variicola MutEb removed 14.6% of Cd2+ from the unsterilized soils while K.variicola MutAc removed 15.6% of Cd2+from the sterilized contaminated soils. However, K.variicola MutAc removed 27.8% and 11.6% of Pb2+ from the unsterilized and sterilized metal contaminated soils respectively. The results indicated that the autochthonous bacteria in the soil assisted in the remediation of the contaminated soil, most importantly, it was observed that the mutant strains performed better than the K.variicola wild type in terms of bioremediation potential, therefore, the strains could be suitable for the remediation of Cd2+ and Pb2+ contaminated soil.