We present initial results from a new high-contrast imaging program dedicated to stars that exhibit long-term Doppler radial velocity accelerations (or "trends"). The goal of the TRENDS (TaRgetting bENchmark-objects with Doppler Spectroscopy) imaging survey is to directly detect and study the companions responsible for accelerating their host star. In this first paper of the series, we report the discovery of low-mass stellar companions orbiting HD 53665, HD 68017, and HD 71881 using NIRC2 adaptive optics (AO) observations at Keck. Follow-up imaging demonstrates association through common proper motion. These comoving companions have red colors with estimated spectral types of K7-M0, M5, and M3-M4, respectively. We determine a firm lower limit to their mass from Doppler and astrometric measurements. In the near future, it will be possible to construct three-dimensional orbits and calculate the dynamical mass of HD 68017 B and possibly HD 71881 B. We already detect astrometric orbital motion of HD 68017 B, which has a projected separation of 13.0 AU. Each companion is amenable to AO-assisted direct spectroscopy. Further, each companion orbits a solar-type star, making it possible to infer metallicity and age from the primary. Such benchmark objects are essential for testing theoretical models of cool dwarf atmospheres.