A near-infrared survey designed to detect widely separated, very low-mass companions to M dwarfs within 8 pc is described. This survey is unique in that it is sensitive to companions with separations of similar to 100-1400 = AU from primaries and with masses down to the 0.03 M(.) level, thereby sampling rarely explored parameter space. In Phase I of this program, described here, candidate stellar and brown dwarf companions are identified by creating color-magnitude plots of all detected point sources in the fields surrounding primaries and searching for objects that are bright enough to be stellar (M(J) less than or equal to 11) or that fall close to theoretical brown dwarf isochrones like GD 165B (M(J) similar to 13). Common proper motion and spectroscopic checks are used to screen candidates. To date, all candidates for which we have made follow-up observations have been identified as background sources and no new low mass stellar or brown dwarf candidates have emerged from this survey. Phase II of this program will include a search for common proper motion between primaries and all field objects to M(J) similar to 17.5, allowing identification of widely separated substellar components, including objects like GL 229B. (C) 1996 American Astronomical Society.