Mitochondria (mt) are double-membraned, dynamic organelles that play an essential role in a large number of cellular processes, and impairments in mt function have emerged as a causative factor for a growing number of human disorders. Given that most biological functions are driven by physical associations between proteins, the first step towards understanding mt dysfunction is to map its protein-protein interaction (PPI) network in a comprehensive and systematic fashion. While mass-spectrometry (MS) based approaches possess the high sensitivity ideal for such an endeavor, it also requires stringent biochemical purification of bait proteins to avoid detecting spurious, non-specific PPIs. Here, we outline a tagging-based affinity purification coupled with mass spectrometry (AP-MS) workflow for discovering new mt protein associations and providing novel insights into their role in mt biology and human physiology/pathology. Because AP-MS relies on the creation of proteins fused with affinity tags, we employ a versatile-affinity (VA) tag, consisting of 3× FLAG, 6 × His, and Strep III epitopes. For efficient delivery of affinity-tagged open reading frames (ORF) into mammalian cells, the VA-tag is cloned onto a specific ORF using Gateway recombinant cloning, and the resulting expression vector is stably introduced in target cells using lentiviral transduction. In this chapter, we show a functional workflow for mapping the mt interactome that includes tagging, stable transduction, selection and expansion of mammalian cell lines, mt extraction, identification of interacting protein partners by AP-MS, and lastly, computational assessment of protein complexes/PPI networks.