We report the first linkage map of tobacco (Nicotiana tabacum L.) generated through microsatellite markers. The microsatellite markers were predominantly derived from genomic sequences of the Tobacco Genome Initiative (TGI) through bioinformatics screening for microsatellite motives. A total of 684 primer pairs were screened for functionality in a panel of 16 tobacco lines. Of those, 637 primer pairs were functional. Potential parents for mapping populations were evaluated for their polymorphism level through genetic similarity analysis. The similarity analysis revealed that the known groups of tobacco varieties (Burley, Flue-cured, Oriental and Dark) form distinct clusters. A mapping population, based on a cross between varieties Hicks Broad Leaf and Red Russian, and consisting of 186 F2 individuals, was selected for mapping. A total of 282 functional microsatellite markers were polymorphic in this population and 293 loci could be mapped together with the morphological trait flower color. Twenty-four tentative linkage groups spanning 1,920 cM could be identified. This map will provide the basis for the genetic mapping of traits in tobacco and for further analyses of the tobacco genome.