Tubulins are still considered as typical proteins of Eukaryotes. However, more recently they have been found in the unusual bacteria Prosthecobacter (btubAB). In this study, the genomic organization of the btub-genes and their genomic environment were characterized by using the newly developed Two-Step Gene Walking method. In all investigated Prosthecobacters, btubAB are organized in a typical bacterial operon. Strikingly, all btub-operons comprise a third gene with similarities to kinesin light chain sequences. The genomic environments of the characterized btub-operons are always different. This supports the hypothesis that this group of genes represents an independent functional unit, which was acquired by Prosthecobacter via horizontal gene transfer. The newly developed Two-Step Gene Walking method is based on randomly primed polymerase chain reaction (PCR). It presents a simple workflow, which comprises only two major steps--a Walking-PCR with a single specific outward pointing primer (step 1) and the direct sequencing of its product using a nested specific primer (step 2). Two-Step Gene Walking proved to be highly efficient and was successfully used to characterize over 20 kb of sequence not only in pure culture but even in complex non-pure culture samples.