Previously, we showed that SAMM50, a mitochondrial outer membrane protein, is N-myristoylated, and this lipid modification is required for the proper targeting of SAMM50 to mitochondria. In this study, we characterized protein N-myristoylation occurring on four human mitochondrial proteins, SAMM50, TOMM40, MIC19, and MIC25, three of which are components of the mitochondrial intermembrane space bridging (MIB) complex, which plays a critical role in the structure and function of mitochondria. In vitro and in vivo metabolic labeling experiments revealed that all four of these proteins were N-myristoylated. Analysis of intracellular localization of wild-type and non-myristoylated G2A mutants of these proteins by immunofluorescence microscopic analysis and subcellular fractionation analysis indicated that protein N-myristoylation plays a critical role in mitochondrial targeting and membrane binding of two MIB components, SAMM50 and MIC19, but not those of TOMM40 and MIC25. Immunoprecipitation experiments using specific antibodies revealed that MIC19, but not MIC25, was a major N-myristoylated binding partner of SAMM50. Immunoprecipitation experiments using a stable transformant of MIC19 confirmed that protein N-myristoylation of MIC19 is required for the interaction between MIC19 and SAMM50, as reported previously. Thus, protein N-myristoylation occurring on two mitochondrial MIB components, SAMM50 and MIC19, plays a critical role in the mitochondrial targeting and protein-protein interaction between these two MIB components.