We present the rationale, first observations and preliminary results of our radial velocity search for exoplanets around M dwarfs. So far we have obtained 2.5 nights (1.5 already done, 2 half nights pending) of Keck NASA time to collect high-resolution near-infrared spectra using NIRSPEC on the KECK II telescope. Our sample consists of 80 nearby (distance ? pc) late M dwarfs (spectral class from M6 through M9) that are not known to be binaries. Earlier observations by our group demonstrated a radial velocity precision ranging from 100 m/s to 400 m/s for late-M dwarfs. Such an accuracy should allow us to detect planets with masses between 2 - 8 MJ at 1 A.U. or 0.7-2.8 MJ at 0.1 A.U, respectively. The goal of this new observational program is to obtain similar or better velocity precision in a larger sample. Spin offs of this program will include the determination of rotational broadening and space velocities for our targets.