Surveys have shown that super-Earth and Neptune-mass exoplanets are more frequent than gas giants around low-mass stars, as predicted by the core accretion theory of planet formation. We report the discovery of a giant planet around the very-low-mass star GJ 3512, as determined by optical and near-infrared radial-velocity observations. The planet has a minimum mass of 0.46 Jupiter masses, very high for such a small host star, and an eccentric 204-day orbit. Dynamical models show that the high eccentricity is most likely due to planet-planet interactions. We use simulations to demonstrate that the GJ 3512 planetary system challenges generally accepted formation theories, and that it puts constraints on the planet accretion and migration rates. Disk instabilities may be more efficient in forming planets than previously thought.