We present the discovery of a comoving planetary-mass companion ~42" (~2000 AU) from a young M3 star, GU Psc, a likely member of the young AB Doradus Moving Group (ABDMG). The companion was first identified via its distinctively red i − z color (>3.5) through a survey made with Gemini-S/GMOS. Follow-up Canada–France–Hawaii Telescope/WIRCam near-infrared (NIR) imaging, Gemini-N/GNIRS NIR spectroscopy and Wide-field Infrared Survey Explorer photometry indicate a spectral type of T3.5 ± 1 and reveal signs of low gravity which we attribute to youth. Keck/Adaptive Optics NIR observations did not resolve the companion as a binary. A comparison with atmosphere models indicates T_eff = 1000–1100 K and log g = 4.5–5.0. Based on evolution models, this temperature corresponds to a mass of 9–13 M_Jup for the age of ABDMG (70–130 Myr). The relatively well-constrained age of this companion and its very large angular separation to its host star will allow its thorough characterization and will make it a valuable comparison for planetary-mass companions that will be uncovered by forthcoming planet-finder instruments such as Gemini Planet Imager and SPHERE.