To obtain a global overview of how mitochondria respond to stress, we aimed to define the plant mitochondrial stress response (MSR). By combining a set of 1196 Arabidopsis thaliana genes that putatively encode mitochondrial proteins with 16 microarray experiments on stress-related conditions, 45 nuclear encoded genes were defined as widely stress-responsive. Using green fluorescent protein (GFP) fusion assays, the mitochondrial targeting of a large number of these proteins was tested, confirming in total 26 proteins as mitochondrially targeted. Several of these proteins were observed to be dual targeted to mitochondria and plastids, including the small heat shock proteins sHSP23.5 and sHSP23.6. In addition to the well defined stress components of mitochondria, such as alternative oxidases, nicotinamide adenine dinucleotide (NAD(P)H) dehydrogenases, and heat shock proteins, a variety of other proteins, many with unknown function, were identified. The mitochondrial carrier protein family was over-represented in the stress-responsive genes, suggesting that stress induces altered needs for metabolite transport across the mitochondrial inner membrane. Although the genes encoding many of these proteins contain common cis-acting regulatory elements, it was apparent that a number of distinct regulatory processes or signals likely triggered the MSR. Therefore, these genes provide new model systems to study mitochondrial retrograde regulation, in addition to the widely used alternative oxidase model. Additionally, as changes in proteins responsive to stress did not correlate well with changes at a transcript level, it suggests that post-transcriptional mechanisms also play an important role in defining the MSR.