To broadly explore mitochondrial structure and function as well as the communication of mitochondria with other cellular pathways, we constructed a quantitative, high-density genetic interaction map (the MITO-MAP) in Saccharomyces cerevisiae. The MITO-MAP provides a comprehensive view of mitochondrial function including insights into the activity of uncharacterized mitochondrial proteins and the functional connection between mitochondria and the ER. The MITO-MAP also reveals a large inner membrane-associated complex, which we term MitOS for mitochondrial organizing structure, comprised of Fcj1/Mitofilin, a conserved inner membrane protein, and five additional components. MitOS physically and functionally interacts with both outer and inner membrane components and localizes to extended structures that wrap around the inner membrane. We show that MitOS acts in concert with ATP synthase dimers to organize the inner membrane and promote normal mitochondrial morphology. We propose that MitOS acts as a conserved mitochondrial skeletal structure that differentiates regions of the inner membrane to establish the normal internal architecture of mitochondria.