Summary Orthogonal Legendre polynomials ( LP ) are used to model the shape of additive genetic and permanent environmental effects in random regression models ( RRM ). Frequently, the Akaike ( AIC ) and the Bayesian ( BIC ) information criteria are employed to select LP order. However, it has been theoretically shown that neither AIC nor BIC is simultaneously optimal in terms of consistency and efficiency. Thus, the goal was to introduce a method, ‘penalizing adaptively the likelihood’ ( PAL ), as a criterion to select LP order in RRM . Four simulated data sets and real data (60 513 records, 6675 Colombian Holstein cows) were employed. Nested models were fitted to the data, and AIC , BIC and PAL were calculated for all of them. Results showed that PAL and BIC identified with probability of one the true LP order for the additive genetic and permanent environmental effects, but AIC tended to favour over parameterized models. Conversely, when the true model was unknown, PAL selected the best model with higher probability than AIC . In the latter case, BIC never favoured the best model. To summarize, PAL selected a correct model order regardless of whether the ‘true’ model was within the set of candidates.