In a search for common proper motion companions using the VISTA Hemisphere Survey (VHS) and the 2MASS catalogs we have identified a very red (J-{{K}s}=2.47 mag) late-L dwarf companion of a previously unrecognized M dwarf VHS J125601.92-125723.9 (hereafter VHS 1256-1257), located at a projected angular separation of 8.″ 06 ± 0.″ 03. In this work we present a suite of astrometric, photometric, and spectroscopic observations of this new pair in an effort to confirm the companionship and characterize the components. From low-resolution (R ∼ 130–600) optical and near-infrared spectroscopy we classified the primary and the companion as M7.5 ± 0.5 and L7 ± 1.5, respectively. The primary shows slightly 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 million years, like the peaked 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 kinematic 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 π = 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 bolometric luminosities of the components and compared them with theoretical evolutionary models to estimate the masses and effective temperatures. For the primary, we determined a luminosity of log ({{L}bol}/{{L}ȯ })=-3.14 ± 0.10, and inferred a mass of 73-15+20 MJup at the boundary between stars and brown dwarfs and an effective temperature of 2620 ± 140 K. For the companion we obtained a luminosity of log ({{L}bol}/{{L}ȯ })=-5.05+/- 0.22 and a mass of 11.2-1.8+9.7 {{M}Jup}, placing it near the deuterium-burning mass limit. The effective temperature derived from evolutionary models is 880-110+140 K, about 400–700 K cooler than the temperature expected for field late-L dwarfs. Based on observations collected at the European Southern Observatory, Chile, programs 092.C-0874 and 293.C-5014(A).