Mycobacterium avium subsp. paratuberculosis causes an enteric infection in cattle, with a great impact on the dairy industry in the United States and worldwide. Characterizing the gene expression profile of M. avium subsp. paratuberculosis exposed to different stress conditions, or shed in cow feces, could improve our understanding of the pathogenesis of M. avium subsp. paratuberculosis. In this report, the stress response of M. avium subsp. paratuberculosis on a genome-wide level (stressome) was defined for the first time using DNA microarrays. Expression data analysis revealed unique gene groups of M. avium subsp. paratuberculosis that were regulated under in vitro stressors while additional groups were regulated in the cow samples. Interestingly, acidic pH induced the regulation of a large number of genes (n=597), suggesting the high sensitivity of M. avium subsp. paratuberculosis to acidic environments. Generally, responses to heat shock, acidity, and oxidative stress were similar in M. avium subsp. paratuberculosis and Mycobacterium tuberculosis, suggesting common pathways for mycobacterial defense against stressors. Several sigma factors (e.g., sigH and sigE) were differentially coregulated with a large number of genes depending on the type of each stressor. Subsequently, we analyzed the virulence of six M. avium subsp. paratuberculosis mutants with inactivation of differentially regulated genes using a murine model of paratuberculosis. Both bacterial and histopathological examinations indicated the attenuation of all gene mutants, especially those selected based on their expression in the cow samples (e.g., lipN). Overall, the employed approach profiled mycobacterial genetic networks triggered by variable stressors and identified a novel set of putative virulence genes. A similar approach could be applied to analyze other intracellular pathogens.