Iron plays a crucial role in metabolism as a key component of catalytic and redox cofactors, such as heme or iron-sulfur clusters in enzymes and electron-transporting or regulatory proteins. Limitation of iron availability by the host is also one of the mechanisms involved in immunity. Pathogens must regulate their protein expression according to the iron concentration in their environment and optimize their metabolic pathways in cases of limitation through the availability of respective cofactors. Trichomonas vaginalis, a sexually transmitted pathogen of humans, requires high iron levels for optimal growth. It is an anaerobe that possesses hydrogenosomes, mitochondrion-related organelles that harbor pathways of energy metabolism and iron-sulfur cluster assembly. We analyzed the proteomes of hydrogenosomes obtained from cells cultivated under iron-rich and iron-deficient conditions employing two-dimensional peptide separation combining IEF and nano-HPLC with quantitative MALDI-MS/MS. We identified 179 proteins, of which 58 were differentially expressed. Iron deficiency led to the upregulation of proteins involved in iron-sulfur cluster assembly and the downregulation of enzymes involved in carbohydrate metabolism. Interestingly, iron affected the expression of only some of multiple protein paralogues, whereas the expression of others was iron independent. This finding indicates a stringent regulation of differentially expressed multiple gene copies in response to changes in the availability of exogenous iron.