It is of great importance to remove petroleum and petroleum-based products from the environment through the genes encoded by the chromosomal and plasmids of microorganisms. This study aimed to compare the petroleum removal efficiencies and plasmid profiles of clinical Klebsiella pneumoniae ATCC 700721 (Kp1) and environmental Klebsiella pneumoniae ATCC 13883 (Kp2) strains. Over 80% of petroleum removal and high bacterial growths were achieved by Kp1 and Kp2 strains. The degradation rate constants and half-life periods of Kp1 and Kp2 strains were 0.262 and 0.280; 2.64 and 2.47 days, respectively. Moreover, the culture supernatants of Kp1 and Kp2 strains reached to 87.5% and 81% in degradation of petroleum. The Gas Chromatography-Mass Spectrometry analysis confirmed that Kp1 and Kp2 strains degraded approximately 90% and 80% of long chain n-alkanes. Kp1 and Kp2 exhibit > 12kbp plasmid DNA band. Plasmid curing was applied with ethidium bromide to determine the role of plasmid and genomic DNA in petroleum degradation. Kp1 and Kp2 strains (plasmid cured) showed over 50% of degradation abilities even in the absence of plasmid DNA. So, the results clearly indicated that both genomic and plasmid DNA of Kp1 and Kp2 contributed to petroleum degradation process. Consequently, the clinical Kp1 and environmental Kp2 strains are promising for further studies as they can be effective in petroleum bioremediation even under unsuitable environmental conditions.