Few data exist on physiological adaptation of M. paratuberculosis (Mptb) in either the host or the environment. The responses of the two distinct strains of Mptb (C and S) to hypoxia and starvation were studied in vitro in this study. The growth pattern of Mptb during stress appeared similar to the dormancy response of other mycobacteria. The C strain was more resistant to starvation stress than the S strain. A total of 66 protein spots differentially expressed in response to starvation and/or hypoxic stress were selected and identified, providing the first functional assessment of the genomic differences known to exist between these strains. Differentially expressed proteins were classified based on biological function and 13 categories were identified including antioxidant enzymes, amino acid metabolism, fatty acid metabolism, ATP and purine biosynthesis, proteolysis, cell wall synthesis, oxidoreducatse enzymes, protein synthesis, signal recognition, hypothetical proteins with putative function, hypothetical proteins with unknown function, cyanate hydrolysis, phosphate metabolism and cell division. These differentially expressed proteins are potential screening targets for future diagnosis, prevention and control of M. paratuberculosis infection and their identification will assist understanding the pathogenesis of the diseases caused by this organism.