Mitochondria constantly fuse and divide to adapt organellar morphology to the cell's ever-changing physiological conditions. Little is known about the molecular mechanisms regulating mitochondrial dynamics. F-box proteins are subunits of both Skp1-Cullin-F-box (SCF) ubiquitin ligases and non-SCF complexes that regulate a large number of cellular processes. Here, we analyzed the roles of two yeast F-box proteins, Mfb1 and Mdm30, in mitochondrial dynamics. Mfb1 is a novel mitochondria-associated F-box protein. Mitochondria in mutants lacking Mfb1 are fusion competent, but they form aberrant aggregates of interconnected tubules. In contrast, mitochondria in mutants lacking Mdm30 are highly fragmented due to a defect in mitochondrial fusion. Fragmented mitochondria are docked but nonfused in Deltamdm30 cells. Mitochondrial fusion is also blocked during sporulation of homozygous diploid mutants lacking Mdm30, leading to a mitochondrial inheritance defect in ascospores. Mfb1 and Mdm30 exert nonredundant functions and likely have different target proteins. Because defects in F-box protein mutants could not be mimicked by depletion of SCF complex and proteasome core subunits, additional yet unknown factors are likely involved in regulating mitochondrial dynamics. We propose that mitochondria-associated F-box proteins Mfb1 and Mdm30 are key components of a complex machinery that regulates mitochondrial dynamics throughout yeast's entire life cycle.