(Abridged) We combine data from The HI Nearby Galaxy Survey and the GALEX Nearby Galaxy Survey to study the relationship between atomic hydrogen (HI) and far-ultraviolet (FUV) emission outside the optical radius (r25) in 17 spiral and 5 dwarf galaxies. In this regime, HI is likely to represent most of the ISM and FUV emission to trace recent star formation with little bias due to extinction, so that the two quantities closely trace the underlying relationship between gas and star formation rate (SFR). The azimuthally averaged HI and FUV intensities both decline with increasing radius in this regime, with the scale length of the FUV profile typically half that of the HI profile. Despite the mismatch in profiles, there is a significant spatial correlation (at 15" resolution) between local FUV and HI intensities; near r25 this correlation is quite strong, in fact stronger than anywhere inside r25, and shows a decline towards larger radii. The star formation efficiency (SFE) - defined as the ratio of FUV/HI and thus the inverse of the gas depletion time - decreases with galactocentric radius across the outer disks, though much shallower than across the optical disks. On average, we find the gas depletion times to be well above a Hubble time (~10^11 yr). We observe a clear relationship between FUV/HI and HI column in the outer disks, with the SFE increasing with increasing HI column. Despite observing systematic variations in FUV/HI, we find no clear evidence for step-function type star formation thresholds. When compared with results from inside r25, we find outer disk star formation to be distinct in several ways: it is extremely inefficient (depletion times of many Hubble times) with column densities and SFRs lower than found anywhere inside the optical disks. It appears that the HI column is one of, perhaps even the key environmental factor in setting the SFR in outer galaxy disks.