We use high-resolution images obtained with the Advanced Camera for Surveys on board the Hubble Space Telescope to determine morphology, nuclear luminosity, and structural parameters of the spheroidal component for a sample of 20 Seyfert galaxies atz = 0.36. We combine these measurements with spectroscopic information from the Keck Telescope to determine the black hole mass-spheroid luminosity relation (MBH-LB), the fundamental plane (FP) of the host galaxies, and the black hole mass-spheroid velocity dispersion relation (MBH-σ). The FP is consistent with that of inactive spheroids at comparable redshifts. Assuming pure luminosity evolution, we find that the host spheroids had smaller luminosity and stellar velocity dispersion than today for a fixed MBH. The offsets correspond to Δ log LB,0 = 0.40 ± 0.11 ± 0.15 (Δlog MBH= 0.51 ± 0.14 ± 0.19) and Δloge σ = 0.13 ± 0.03 ± 0.05 (Δlog MBH = 0.54 ± 0.12 ± 0.21), respectively, for the MBH-L and M BH-σ relations (the double error bars indicate random and ystematic uncertainties, respectively). A detailed analysis of known systematic errors and selection effects shows that they cannot account for the observed offset. We conclude that the data are inconsistent with pure luminosity evolution and the existence of universal and tight scaling relations. In order to obey the three local scaling relations by z = 0, assuming no significant black hole growth, the distant spheroids have to grow their stellar mass by approximately 60% (Δ log Msph = 0.20 ± 0.14) in the next 4 billion years, while preserving their size and holding their stellar mass-to-light ratio approximately constant. The measured evolution can be expressed as MBH/Msph ∝ (1 + z) 1.5±1.0, consistent with black holes of a few × 10 8 M⊙ completing their growth before their host galaxies. Based on the disturbed morphologies of a fraction of the sample (6/20), we suggest collisional mergers with disk-dominated systems as the physical mechanism driving the evolution. © 2007. The American Astronomical Society. All rights reserved.