A powerful approach to understand protein structure and evolution is to perform computer simulations that mimic aspects of evolution. In particular, structure-based computational protein design (CPD) can address the inverse folding problem, exploring a large space of amino acid sequences and selecting ones predicted to adopt a given fold. Previously, CPD has been used to entirely redesign several proteins: all or most of the protein sequence was allowed to mutate freely; among sampled sequences, those with low computed folding energy were selected, and a few percent of them did indeed adopt the correct fold. Those studies used an energy function that was partly or largely knowledge-based, with several empirical terms. Here, we show that a PDZ domain can be entirely redesigned using a “physics-based” energy function that combines standard molecular mechanics and a recent, continuum electrostatic solvent model. Many thousands of sequences were generated by Monte Carlo simulation. Among the lowest-energy sequences, three were chosen for experimental testing. All three could be overexpressed and had native-like circular dichroism and 1D NMR spectra. Two exhibited an upshift of their thermal denaturation curves when a peptide ligand was present, indicating binding and suggesting correctly folded proteins. Evidently, the physical principles that govern molecular mechanics and continuum electrostatics are sufficient to perform whole-protein redesign. This is encouraging, since these methods provide physical insights, can be systematically improved, and are transferable to other biopolymers and ligands of medical or technological interest.