We describe the first results from the Outer Limits Survey, an NOAO survey designed to detect, map, and characterize the extended structure of the Large and Small Magellanic Clouds (LMC and SMC). The survey consists of deep images of 55 0 degrees.6 x 0 degrees.6 fields distributed at distances up to 20 degrees from the Clouds, with 10 fields at larger distances representing controls for contamination by Galactic foreground stars and background galaxies. The field locations probe the outer structure of both the LMC and SMC, as well as exploring areas defined by the Magellanic Stream, the Leading Arm, and the LMC orbit as recently measured from its proper motion. The images were taken with C, M, R, I, and DDO51 filters on the CTIO Blanco 4 m telescope and Mosaic2 camera, with supporting calibration observations taken at the CTIO 0.9m telescope. The CRI images reach depths below the oldest main-sequence (MS) turnoffs at the distance of the Clouds, thus yielding numerous probes of structure combined with good ability to measure stellar ages and metallicities. The M and DDO51 images allow for discrimination of LMC and SMC giant stars from foreground dwarfs, allowing us to use giants as additional probes of Cloud structure and populations. From photometry of eight fields located at radii of 7 degrees-19 degrees north of the LMC bar, we find MS stars associated with the LMC out to 16 degrees from the LMC center, while the much rarer giants can only be convincingly detected out to 11 degrees. In one field, designated as a control, we see the unmistakable signature of the Milky Way (MW) globular cluster NGC 1851, which lies several tidal radii away from the field center. The color-magnitude diagrams show that while at 7 degrees radius LMC populations as young as 500 Myr are present, at radii greater than or similar to 11 degrees only the LMC's underlying old metal-poor ([M/H]similar to - 1) population remains, demonstrating the existence of a mean population gradient at these radii. Nevertheless, even at extreme large distances, the dominant age is significantly younger than that of the Galactic globular clusters. The MS star counts follow an exponential decline with distance with a scale length of 1.15 kpc, essentially the same scale length as gleaned for the inner LMC disk from prior studies. While we cannot rule out the existence of undetected tidal features elsewhere in the LMC periphery, the detection of an ordered structure to 12 disk scale lengths is unprecedented and adds to the puzzle of the LMC's interaction history with the SMC and the MW. Our results do not rule out the possible existence of an LMC stellar halo, which we show may only begin to dominate over the disk at still larger radii than where we have detected LMC populations.