To contribute to Mycobacterium bovis BCG characterization, two substrains were analyzed using two-dimensional gel electrophoresis (2D-PAGE) and mass spectrometry (MS), based on their protective efficacy in a pulmonary-tuberculosis mouse model. Cell-fraction proteins of BCG Denmark and Phipps substrains were separated into 500 spots in 2D-PAGE. The proteomes were similar in protein number, and isoelectric point (pI) and molecular mass (MM) distribution. Statistical analysis, resulted in 72 spots with no change, and 168 and 90 unique for BCG Phipps or Denmark, respectively. Two hundred and fourteen spots showed changes in intensity of >1-fold, 138 of Denmark, and 76 of Phipps. Seventeen spots were selected for MS-based identification (13 from Phipps and 4 from Denmark), including unique, as well as proteins with changes in intensity. The proteins identified participate in virulence, detoxification, adaptation, lipid metabolism, information pathways, cell wall and cell processes, intermediary metabolism and respiration, or still hypotheticals. Our findings contribute to phenotype characterization of BCG substrains and provide new elements to consider for the design of diagnostic tools, drug targets and a new vaccine against tuberculosis based upon protein expression through quantitative statistical analysis.