  Given an exceptional compact simple Lie group $G$ we describe new
left-invariant Einstein metrics which are not naturally reductive. In
particular, we consider fibrations of $G$ over flag manifolds with a certain
kind of isotropy representation and we construct the Einstein equation with
respect to the induced left-invariant metrics. Then we apply a technique based
on Gr\"obner bases and classify the real solutions of the associated algebraic
systems. For the Lie group ${\rm G}_2$ we obtain the first known example of a
left-invariant Einstein metric, which is not naturally reductive. Moreover, for
the Lie groups ${\rm E}_7$ and ${\rm E}_8$, we conclude that there exist
non-isometric non-naturally reductive Einstein metrics, which are ${\rm
Ad}(K)$-invariant by different Lie subgroups $K$.
