Most statistical software packages implement numerical strategies for computation of maximum likelihood estimates in random effects models. Little is known, however, about the algebraic complexity of this problem. For the one-way layout with random effects and unbalanced group sizes, we give formulas for the algebraic degree of the likelihood equations as well as the equations for restricted maximum likelihood estimation. In particular, the latter approach is shown to be algebraically less complex. The formulas are obtained by studying a univariate rational equation whose solutions correspond to the solutions of the likelihood equations. Applying techniques from computational algebra, we also show that balanced two-way layouts with or without interaction have likelihood equations of degree four. Our work suggests that algebraic methods allow one to reliably find global optima of likelihood functions of linear mixed models with a small number of variance components.