The exchange of ADP and ATP across the inner mitochondrial membrane is a fundamental cellular process. This exchange is facilitated by the adenine nucleotide translocase, the structure and function of which are critically dependent on the signature phospholipid of mitochondria, cardiolipin (CL). Here we employ multiscale molecular dynamics simulations to investigate CL interactions within a membrane environment. Using simulations at both coarse-grained and atomistic resolutions, we identify three CL binding sites on the translocase, in agreement with those seen in crystal structures and inferred from nuclear magnetic resonance measurements. Characterization of the free energy landscape for lateral lipid interaction via potential of mean force calculations demonstrates the strength of interaction compared to those of binding sites on other mitochondrial membrane proteins, as well as their selectivity for CL over other phospholipids. Extending the analysis to other members of the family, yeast Aac2p and mouse uncoupling protein 2, suggests a degree of conservation. Simulation of large patches of a model mitochondrial membrane containing multiple copies of the translocase shows that CL interactions persist in the presence of protein-protein interactions and suggests CL may mediate interactions between translocases. This study provides a key example of how computational microscopy may be used to shed light on regulatory lipid-protein interactions.