The tumor suppressor protein p53 regulates numerous signaling pathways by specifically recognizing diverse p53 response elements (REs). Understanding the mechanisms of p53-DNA interaction requires structural information on p53 REs. However, such information is limited as a 3D structure of any RE in the unbound form is not available yet. Here, site-directed spin labeling was used to probe the solution structures of REs involved in p53 regulation of the p21 and Bax genes. Multiple nanometer distances in the p21-RE and BAX-RE, measured using a nucleotide-independent nitroxide probe and double-electron-electron-resonance spectroscopy, were used to derive molecular models of unbound REs from pools of all-atom structures generated by Monte-Carlo simulations, thus enabling analyses to reveal sequence-dependent DNA shape features of unbound REs in solution. The data revealed distinct RE conformational changes on binding to the p53 core domain, and support the hypothesis that sequence-dependent properties encoded in REs are exploited by p53 to achieve the energetically most favorable mode of deformation, consequently enhancing binding specificity. This work reveals mechanisms of p53-DNA recognition, and establishes a new experimental/computational approach for studying DNA shape in solution that has far-reaching implications for studying protein-DNA interactions.