In a search for common proper motion companions using the VISTA Hemisphere Survey and 2MASS catalogs we have identified a very red (J-Ks=2.47 mag) late-L dwarf companion of a previously unrecognized M dwarf VHS J125601.92-125723.9, located at a projected angular separation of 8.06"+/-0.03". From low-resolution optical and near-IR spectroscopy we classified the primary and the companion as an M7.5+/-0.5 and L7+/-1.5, respectively. The primary shows weaker alkali lines than field dwarfs of similar spectral type, but still consistent with either a high-gravity dwarf or a younger object of hundreds of millions of years. The secondary shows spectral features characteristic for low surface gravity objects at ages below several hundred Myr, like the triangular shape of the H-band continuum and alkali lines weaker than in field dwarfs of the same spectral type. The absence of lithium in the atmosphere of the primary and the likely membership to the Local Association allowed us to constrain the age of the system to the range of 150-300 Myr. We report a measurement of the trigonometric parallax pi=78.8+/-6.4 mas, which translates into a distance of 12.7+/-1.0 pc; the pair thus has a projected physical separation of 102+/-9 AU. We derived the Lbol of the components and compared them with theoretical evolutionary models to estimate the masses and effective temperatures. For the primary, we determined log(Lbol/LSun)=-3.14+/-0.10, and a mass of 73 (+20,-15} MJup at the boundary between stars and brown dwarfs and Teff of 2620+/-140 K. For the companion we obtained log(Lbol/LSun)=-5.05+/-0.22 and a mass of 11.2 (+9.7,-1.8) MJup placing it near the deuterium-burning mass limit. The effective temperature derived from evolutionary models is 880 (+140,-110) K, about 400-700 K cooler than expected for field late-L dwarfs. ; Comment: 19 pages, 13 figures. Accepted for publication in ApJ