Myoglobin (Mb) interaction with the outer mitochondrial membrane (OMM) promotes oxygen (O) release. However, comprehensive molecular details on specific contact regions of the OMM with oxygenated (oxy-) and deoxygenated (deoxy-)Mb are missing. We used molecular dynamics (MD) simulations to explore the interaction of oxy- and deoxy-Mb with the membrane lipids of the OMM in two lipid compositions: (a) a typical whole membrane on average, and (b) specifically the cardiolipin-enriched cristae region (contact site). Unrestrained relaxations showed that on average, both the oxy- and deoxy-Mb established more stable contacts with the lipids typical of the cristae contact site, then with those of the average OMM. However, in steered detachment simulations, deoxy-Mb clung more tightly to the average OMM, and oxy-Mb strongly preferred the contact sites of the OMM. The MD simulation analysis further indicated that a non-specific binding, mediated by local electrostatic interactions, existed between charged or polar groups of Mb and the membrane, for stable interaction. To the best of our knowledge, this is the first computational study providing the molecular details of the direct Mb-mitochondria interaction that assisted in distinguishing the preferred localization of oxy- and deoxy-Mb on the OMM. Our findings support the existing experimental evidence on Mb-mitochondrial association and shed more insights on Mb-mediated O transport for cellular bioenergetics.