Double electron-electron resonance (DEER) spectroscopy is a powerful experimental technique for understanding the conformational heterogeneity of proteins. It involves attaching nitroxide spin labels to two residues in the protein to obtain a distance distribution between them. However, the choice of residue pairs to label in the protein, requires cautious thought and experimentalists are required to pick label positions from a large set of all possible residue pair combinations in the protein. In this paper, we address the problem of the choice of DEER spin label positions in a protein. For this purpose, we utilize all-atom Molecular Dynamics simulations of protein dynamics, to rank the sets of labeled residues pairs in terms of their ability to capture the conformational dynamics of the protein. Our design methodology is based on the following two criteria: 1) an ideal set of DEER spin label positions should capture the slowest conformational change processes observed in the protein dynamics and 2) any two sets of residue pairs should describe orthogonal conformational change processes to maximize the overall information gain and reduce the number of labeled residues pairs. We utilize Markov State Models of protein dynamics to identify slow dynamical processes and a genetic algorithm based approach to predict the optimal residue pair choices with limited computational time requirement. We predict the optimal residue pairs for DEER spectroscopy in β2 Adrenergic Receptor, C-terminal domain of calmodulin and peptide transporter PepTSo. We find that our choices are ranked higher than those used to perform DEER experiments on the proteins investigated in this study. Hence, the predicted DEER residue pair choices determined from our method provide maximum insight into the conformational heterogeneity of the protein while using the minimum number of labeled residues.