We describe here the complete genome sequence of a common clone of Mycobacterium avium subspecies paratuberculosis (Map) strain K-10, the causative agent of Johne's disease in cattle and other ruminants. The K-10 genome is a single circular chromosome of 4,829,781 base pairs and encodes 4,350 predicted ORFs, 45 tRNAs, and one rRNA operon. In silico analysis identified >3,000 genes with homologs to the human pathogen, M. tuberculosis (Mtb), and 161 unique genomic regions that encode 39 previously unknown Map genes. Analysis of nucleotide substitution rates with Mtb homologs suggest overall strong selection for a vast majority of these shared mycobacterial genes, with only 68 ORFs with a synonymous to nonsynonymous substitution ratio of >2. Comparative sequence analysis reveals several noteworthy features of the K-10 genome including: a relative paucity of the PE/PPE family of sequences that are implicated as virulence factors and known to be immunostimulatory during Mtb infection; truncation in the EntE domain of a salicyl-AMP ligase (MbtA), the first gene in the mycobactin biosynthesis gene cluster, providing a possible explanation for mycobactin dependence of Map; and Map-specific sequences that are likely to serve as potential targets for sensitive and specific molecular and immunologic diagnostic tests. Taken together, the availability of the complete genome sequence offers a foundation for the study of the genetic basis for virulence and physiology in Map and enables the development of new generations of diagnostic tests for bovine Johne's disease.