We present the first results from our Red Optical Planet Survey to search for low-mass planets orbiting late-type dwarfs (M5.5VM9V) in their habitable zones. Our observations with the red arm of the Magellan Inamori Kyocera Echelle spectrograph (0.50.9 m) at the 6.5-m Magellan Clay telescope at Las Campanas Observatory indicate that =92 per cent of the flux lies beyond 0.7 m. We use a novel approach that is essentially a hybrid of the simultaneous iodine and ThAr methods for determining precision radial velocities. We apply least squares deconvolution to obtain a single high signal-to-noise ratio (S/N) stellar line for each spectrum and cross-correlate against the simultaneously observed telluric line profile, which we derive in the same way. Utilizing the 0.620.90 m region, we have achieved an rms precision of 10 ms-1 for an M5.5V spectral type star with spectral S/N 160 on 5-min time-scales. By M8V spectral type, a precision of 30 ms-1 at S/N = 25 is suggested, although more observations are needed. An assessment of our errors and scatter in the radial velocity points hints at the presence of stellar radial velocity variations. Of our sample of seven stars, two show radial velocity signals at 6s and 10s of the cross-correlation uncertainties. We find that chromospheric activity (via Ha variation) does not have an impact on our measurements and are unable to determine a relationship between the derived photospheric line profile morphology and radial velocity variations without further observations. If the signals are planetary in origin, our findings are consistent with estimates of Neptune mass planets that predict a frequency of 1327 per cent for early M dwarfs. Our current analysis indicates the we can achieve a sensitivity that is equivalent to the amplitude induced by a 6 M? planet orbiting in the habitable zone. Based on simulations, we estimate that <10 M? habitable zone planets will be detected in a new stellar mass regime, with =20 epochs of observations. Higher resolution and greater instrument stability indicate that photon-limited precisions of 2 ms-1 are attainable on moderately rotating M dwarfs (with vsin i= 5 km s-1) using our technique.