Doppler spectroscopy has detected 136 planets around nearby stars. A major puzzle is why their orbits are highly eccentric, while all planets in our Solar System are on nearly circular orbits, as expected if they formed by accretion processes in a protostellar disk. Several mechanisms have been proposed to generate large eccentricities after planet formation, but so far there has been little observational evidence to support any particular one. Here we report that the current orbital configuration of the three giant planets around Upsilon Andromedae (ups And) provides evidence for a close dynamical interaction with another planet, now lost from the system. The planets started on nearly circular orbits, but chaotic evolution caused the outer planet (ups And d) to be perturbed suddenly into a higher-eccentricity orbit. The coupled evolution of the system then causes slow periodic variations in the eccentricity of the middle planet (ups And c). Indeed, we show that ups And c periodically returns to a very nearly circular state every 9000 years. Our analysis shows that strong planet-planet scattering, one of several mechanisms previously discussed for increasing orbital eccentricities, must have operated in this system.