The conserved AAA-ATPase Msp1 is embedded in the outer mitochondrial membrane and removes mislocalized tail-anchored (TA) proteins upon dysfunction of the guided entry of tail-anchored (GET) pathway. It remains unclear how Msp1 recognizes its substrates. Here, we extensively characterize Msp1 and its substrates, including the mitochondrially targeted Pex15Δ30, and full-length Pex15, which mislocalizes to mitochondria upon dysfunction of Pex19 but not the GET pathway. Moreover, we identify two new substrates, Frt1 and Ysy6. Our results suggest that mislocalized TA proteins expose hydrophobic surfaces in the cytoplasm and are recognized by Msp1 through conserved hydrophobic residues. Introducing a hydrophobic patch into mitochondrial TA proteins transforms them into Msp1 substrates. In addition, Pex15Δ30 and Frt1 contain basic inter-membrane space (IMS) residues critical for their mitochondrial mistargeting. Remarkably, Msp1 recognizes this feature through the acidic D12 residue in its IMS domain. This dual-recognition mechanism involving interactions at the cytoplasmic and IMS domains of Msp1 and substrates greatly facilitates substrate recognition and is required by Msp1 to safeguard mitochondrial functions.