We present the discovery of a co-moving planetary-mass companion ~42 (~2000 AU) from a young M3 star, GU Psc, 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 Teff = 1000-1100 K and logg = 4.5-5.0. Based on evolution models, this temperature corresponds to a mass of 9-13 MJup 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.