Random effects models are commonly used parametric models in the analysis of longitudinal data. Selection of covariates and the variance-covariance matrix structure is crucial to the accuracy of estimation and prediction in random effects models. Most selection procedures used for random effects models (for example, AIC, BIC, and RIC) penalize increasing model size through a fixed penalty parameter. We derive generalized degrees of freedom (GDF) for linear random effects models and use the GDF to define a data-adaptive complexity penalty for model selection. Data perturbation is employed to estimate the GDF of linear random effects models. The data-adaptive procedure outperforms information criteria (AIC, BIC) both for large and for small models. Simulation results support the effectiveness of the new procedure for modeling longitudinal data. Potential pursuits in the future are adaptive selection of generalized random effects models or nonlinear random effects models.