Many mitochondrial proteins are synthesized as precursors in the cytosol with an N-terminal mitochondrial targeting sequence (MTS) which is cleaved off upon import. Although much is known about import mechanisms and MTS structural features, the variability of MTS still hampers robust sub-cellular software predictions. Here, we took advantage of two paralogous late embryogenesis abundant proteins (LEA) from Arabidopsis with different subcellular locations to investigate structural determinants of mitochondrial import and gain insight into the evolution of the LEA genes. LEA38 and LEA2 are short proteins of the LEA_3 family, which are very similar along their whole sequence, but LEA38 is targeted to mitochondria while LEA2 is cytosolic. Differences in the N-terminal protein sequences were used to generate a series of mutated LEA2 which were expressed as GFP-fusion proteins in leaf protoplasts. By combining three types of mutation (substitution, charge inversion, and segment replacement), we were able to redirect the mutated LEA2 to mitochondria. Analysis of the effect of the mutations and determination of the LEA38 MTS cleavage site highlighted important structural features within and beyond the MTS. Overall, these results provide an explanation for the likely loss of mitochondrial location after duplication of the ancestral gene.