  We analyze Yukawa unification in the the context of $E_8\times E_8$ heterotic
Calabi-Yau models which rely on breaking to a GUT theory via a non-flat gauge
bundle and subsequent Wilson line breaking to the standard model. Our focus is
on underlying GUT theories with gauge group $SU(5)$ or $SO(10)$. We provide a
detailed analysis of the fact that, in contrast to traditional field theory
GUTs, the underlying GUT symmetry of these models does not enforce Yukawa
unification. Using this formalism, we present various scenarios where Yukawa
unification can occur as a consequence of additional symmetries. These
additional symmetries arise naturally in some heterotic constructions and we
present an explicit heterotic line bundle model which realizes one of these
scenarios.
