Plants respond to environmental pollutants such as heavy metal(s) by triggering the expression of genes that encode proteins involved in stress response. Toxic metal ions profoundly affect the cellular protein homeostasis by interfering with the folding process and aggregation of nascent or non-native proteins leading to decreased cell viability. However, plants possess a range of ubiquitous cellular surveillance systems that enable them to efficiently detoxify heavy metals toward enhanced tolerance to metal stress. As proteins constitute the major workhorses of living cells, the chelation of metal ions in cytosol with phytochelatins and metallothioneins followed by compartmentalization of metals in the vacuoles as well as the repair of stress-damaged proteins or removal and degradation of proteins that fail to achieve their native conformations are critical for plant tolerance to heavy metal stress. In this review, we provide a broad overview of recent advances in cellular protein research with regards to heavy metal tolerance in plants. We also discuss how plants maintain functional and healthy proteomes for survival under such capricious surroundings.