We have conducted a novel search of most of the southern sky for nearby red dwarfs having low proper motions, with specific emphasis on those with proper motion < 0.18 arcsec yr-1, the lower cutoff of Luytens classic proper motion catalog. We used a tightly constrained search of the SuperCOSMOS database and a suite of photometric distance relations for photographic BRI and 2MASS JHKs magnitudes to estimate distances to more than fourteen million red dwarf candidates. Here we discuss 29 stars in 26 systems estimated to be within 25 parsecs, all of which have pm < 0.18 arcsec yr-1, which we have investigated using milliarcsecond astrometry, VRI photometry, and low-resolution spectroscopy. In total, we present the first parallaxes of 20 star systems, nine of which are within 25 parsecs. We have additionally identified eight young M dwarfs, of which two are new members of the nearby young moving groups, and 72 new giants, including two new carbon stars. We also present the entire catalog of 1215 sources we have identified by this means.