Background: Many non-tuberculous mycobacteria synthesize abundant glycopeptidolipids (GPLs). These surface-located GPLs are involved in pathogenicity by interfering with the host immune system. In Mycobacterium avium subsp. avium (Mav), GPLs consist of a lipopeptide core composed of a tetrapeptide O-linked to mono- and oligo-saccharides. The biosynthesis pathway of the simplest GPLs is now relatively well understood and involves probably more than fifteen genes. Whereas it is very obvious that most, if not all, of the Mav isolates produce GPLs, the picture is not as clear for M. avium subsp. paratuberculosis (Map), the etiologic agent of Johne's disease in cattle, and several conflicting data have been produced. Methods: Biochemical analysis of a large set of characterized Map isolates showed that all Map strains tested produce a lipopentapeptide (L5P) instead of GPLs. To provide a genomic basis for the synthesis of this compound, the recently published genome sequence of Map was explored using in silica methods. Even though Map produces a lipopeptide rather than GPL, its genome contains nevertheless a locus highly similar to the GPL biosynthetic pathway of Mav. We showed that the module composition of the non-ribosomal protein synthase (Nrp) of Map, the enzyme involved in the synthesis of the peptidyl moiety, is dramatically different from that of other GPL producers such as M. smegmatis (Ms) and Mav and is in agreement with the amino acid content of the L5P We also showed that the peptidyl moiety of the L5P is a target for a strong specific humoral response in Map infected animals. Conclusions: These genomic and biochemical differences may help to unambiguously distinguish Map from Mav and also from M. bovis, to reclassify related strains of the Map species and to allow the convenient and specific diagnosis of paratuberculosis.