We present the discovery of a wide (67 AU) substellar companion to the nearby (21 pc) young solar-metallicity M1 dwarf CD-35 2722, a member of the ~100 Myr AB Doradus association. Two epochs of astrometry from the NICI Planet-Finding Campaign confirm that CD-35 2722 B is physically associated with the primary star. Near-IR spectra indicate a spectral type of L4±1 with a moderately low surface gravity, making it one of the coolest young companions found to date. The absorption lines and near-IR continuum shape of CD-35 2722 B agree especially well the dusty field L4.5 dwarf 2MASS J22244381-0158521, while the near-IR colors and absolute magnitudes match those of the 5 Myr old L4 planetary-mass companion, 1RXS J160929.1-210524 b. Overall, CD-35 2722 B appears to be an intermediate-age benchmark for L-dwarfs, with a less peaked H-band continuum than the youngest objects and near-IR absorption lines comparable to field objects. We fit Ames-Dusty model atmospheres to the near-IR spectra and find T=1700-1900 K and log(g) =4.5±0.5. The spectra also show that the radial velocities of components A and B agree to within ±10 km/s, further confirming their physical association. Using the age and bolometric luminosity of CD-35 2722 B, we derive a mass of 31±8 Mjup from the Lyon/Dusty evolutionary models. Altogether, young late-M to mid-L type companions appear to be over-luminous for their near-IR spectral type compared to field objects, in contrast to the under-luminosity of young late-L and early-T dwarfs.