Conformational flexibility is key to the function of many proteins and is thus an important focus for effective computational modeling. Sampling side-chain degrees of freedom has been an integral part of many successful computational protein design methods, and backbone flexibility is increasingly being used in these efforts. The predictions of these approaches, however, have not been directly compared to experimental measurements of side-chain and backbone solution-state conformational variability. Here, we describe methods for validating side-chain and backbone flexibility modeling by comparing to two sets of solution state Nuclear Magnetic Resonance (NMR) measurements: side chain relaxation order parameters 17 proteins totaling 530 data points, and backbone amide residual dipolar couplings (RDCs) of ubiquitin in 23 alignment media. The model for backbone flexibility that we use is the "Backrub" method; a Monte Carlo protocol combining rotamer changes with motions inspired by alternative conformations observed in sub-Angstrom resolution crystal structures. First, for modeling side chain conformational variability, we use a Monte Carlo approach comparing sampling of side chains with and without backbone flexibility. Our results indicate that the fixed-backbone model performs reasonably well but including backbone flexibility leads to significant improvements in modeling side-chain order parameters. Second, we focus on modeling backbone flexibility and we present an ensemble of ubiquitin in solution that is created by first sampling conformational space without experimental information using "Backrub" motions, and then refining with residual dipolar coupling measurements (RDCs) to select the final members of the ensemble. We show that the ubiquitin Backrub ensemble is simultaneously consistent with conformational dynamics reflected in the RDCs, the conformational variability present in ubiquitin complex structures, and characteristics of the conformational and sequence diversity of ubiquitin homologs. Our ensemble representation thus supports an overall relation between native-state protein dynamics and evolutionarily sampled sequence space. The presented insights into flexibility and the methods we have developed can be applied to numerous modeling tasks, including improved modeling of sequence diversity in protein design simulations, prediction of correlated motions within proteins, and design of sequence libraries for experimental selection.