The original strategy used in the Sulfolobus solfatnricus genome project was to sequence non overlapping, or minimally overlapping, cosmid or lambda inserts without constructing a physical map. However, after only about two thirds of the genome sequence was completed, this approach became counter-productive because there was a high sequence bias in the cosmid and lambda libraries. Therefore, a new approach was devised for linking the sequenced regions which may be generally applicable. BAC libraries were constructed and terminal sequences of the clones were determined and used for both end mapping and PCR screening. The PCR approaches included a novel chromosome walking method termed “paired-PCR”. 21 gaps were filled by BAC end sequence analyses and 6 gaps were filled by PCR including three large ones by paired-PCR. The complete map revealed that 0.9 Mb remained to be sequenced and 34 BAC clones were selected for walking over small gaps and preparing template libraries for larger ones. It is concluded that an optimal strategy for sequencing microorganism genomes involves construction of a high-resolution physical map by BAC end analyses, PCR screening and paired-PCR chromosome walking after about half the genome sequence has been accumulated.