In order to successfully enter the latent stage, Mycobacterium tuberculosis must adapt to conditions such as nutrient limitation and hypoxia. In vitro models that mimic latent infection are valuable tools for describing the changes in metabolism that occur when the bacterium exists in a non-growing form. We used two complementary proteomic approaches, label-free LC-MS/MS analysis and two-dimensional difference gel electrophoresis, to determine the proteome profile of extracellular proteins from M. tuberculosis cultured under nutrient starvation. Through the label-free LC-MS/MS analysis of fractionated samples, 1176 proteins were identified from culture filtrates of log phase and nutrient-starved cultures, and the protein levels of 230 proteins were increased in nutrient-starved culture filtrates, whereas those of 208 proteins were decreased. By means of Gene Ontology clustering analysis, significant differences in the overall metabolism during nutrient starvation were detected. Notably, members of the toxin–antitoxin systems were present in larger quantities in nutrient-starved cultures, supporting a role for these global modules as M. tuberculosis switches its metabolism into dormancy. Decreased abundance of proteins involved in amino acid and protein synthesis was apparent, as well as changes in the lipid metabolism. Further analysis of the dataset identified increased abundance of lipoproteins and decreased abundance of ESAT-6 family proteins. Results from the two-dimensional difference gel electrophoresis proteomics demonstrated overall agreement with the LC-MS/MS data and added complementary insights about protein degradation and modification.