A new class of ultra-long-duration (more than 10,000 seconds) γ-ray bursts has recently been suggested. They may originate in the explosion of stars with much larger radii than those producing normal long-duration γ-ray bursts or in the tidal disruption of a star. No clear supernova has yet been associated with an ultra-long-duration γ-ray burst. Here we report that a supernova (SN 2011kl) was associated with the ultra-long-duration γ-ray burst GRB 111209A, at a redshift z of 0.677. This supernova is more than three times more luminous than type Ic supernovae associated with long-duration γ-ray bursts, and its spectrum is distinctly different. The slope of the continuum resembles those of super-luminous supernovae, but extends further down into the rest-frame ultraviolet implying a low metal content. The light curve evolves much more rapidly than those of super-luminous supernovae. This combination of high luminosity and low metal-line opacity cannot be reconciled with typical type Ic supernovae, but can be reproduced by a model where extra energy is injected by a strongly magnetized neutron star (a magnetar), which has also been proposed as the explanation for super-luminous supernovae.