Four circular cryptic plasmids were detected from propene-degrading Rhodococcus rhodochrous (formerly Nocardia corallina) B-276 and the smallest 7.6-kb plasmid, named pNC500 was used to construct Rhodococcus-E. coli shuttle vector, pNC5403. Sequence analysis of pNC500 revealed that the plasmid contains eight potential ORFs, namely 1 through 8. The deduced amino acid sequences for ORFs 3, 4, 6, and 7 show homology with those of Rep A, Rep B, DNA methyl-transferase (M.XamI), and restriction nuclease (R.XamI), respectively. The region responsible for replication in the potent oil-desulfurization bacterium, Rhodococcus opacus T09 was determined as 3.7 kb-XbaI/BalI fragment which contains ORFs 3 and 4, while no transformants were obtained when ORF 4 was partially deleted, suggesting that both are required for its replication. Alignment of the predicted amino acid sequences revealed that ORFs 3 and 4 were DNA binding protein and DNA primase, respectively. A compatibility test with pAL5000-related plasmid vector, pRHK1, which contains pRC4, revealed that pNC5403 was compatible with pRHK1 suggesting that each replication origin would be different. ORFs 3 and 4 containing a pNC5403 derivative, pN5DXB, was stably maintained for over 80 generations in the absence of antibiotic selective conditions.