We present the resolved stellar populations in the inner and outer halo of the nearby lenticular galaxy NGC~3115. Using deep HST observations, we analyze stars two magnitudes fainter than the tip of the red giant branch (TRGB). We study three fields along the minor axis of this galaxy, 19, 37 and 54 kpc from its center -- corresponding to 7, 14, 21 effective radii (r_{e}). Even at these large galactocentric distances, all of the fields are dominated by a relatively enriched population, with the main peak in the metallicity distribution decreasing with radius from [Z/H] ~ -0.5 to -0.65. The fraction of metal-poor stars ([Z/H] < -0.95) increases from 17%, at 16-37 kpc, to 28%, at ~54 kpc. We observe a distinct low metallicity population (peaked at [Z/H] ~ -1.3 and with total mass 2*10^{10}M_{odot} ~ 14% of the galaxys stellar mass) and argue that this represents the detection of an underlying low metallicity stellar halo. Such halos are generally predicted by galaxy formation theories and have been observed in several late type galaxies including the Milky Way and M31. The metallicity and spatial distribution of the stellar halo of NGC~3115 are consistent with the galaxys globular cluster system, which has a similar low metallicity population that becomes dominant at these large radii. This finding supports the use of globular clusters as bright chemo-dynamical tracers of galaxy halos. These data also allow us to make a precise measurement of the magnitude of the TRGB, from which we derive a distance modulus of NGC~3115 of 30.05pm0.05pm0.10_{sys} (10.2pm0.2pm0.5_{sys} Mpc).