The origin of the observed masses and mixing angles of quarks and leptons is one of imperative subjects in and beyond the standard model. Toward a deeper understanding of flavor structure, we investigate in this paper the minimality of fermion mass (Yukawa) matrices in unified theory. That is, the simplest matrix form is explored in light of the current experimental data for quarks and leptons, including the recent measurements of quark CP violation and neutrino oscillations. Two types of neutrino mass schemes are particularly analyzed; (i) Majorana masses of left-handed neutrinos with unspecified mechanism and (ii) Dirac and Majorana masses introducing three right-handed neutrinos. As a result, new classes of neutrino mass matrices are found to be consistent to the low-energy experimental data and high-energy unification hypothesis. For distinctive phenomenological implications of the minimal fermion mass textures, we discuss flavor-violating decay of charged leptons, the baryon asymmetry of the universe via thermal leptogenesis, neutrino-less double beta decay, and low-energy leptonic CP violation.