New astrometric reductions of the US Naval Observatory CCD Astrograph Catalog (UCAC) all-sky observations were performed from first principles using the TGAS stars in the 8 to 11 magnitude range as reference star catalog. Significant improvements in the astrometric solutions were obtained and the UCAC5 catalog of mean positions at a mean epoch near 2001 was generated. By combining UCAC5 with Gaia DR1 data new proper motions on the Gaia coordinate system for over 107 million stars were obtained with typical accuracies of 1 to 2 mas/yr (R = 11 to 15 mag), and about 5 mas/yr at 16th mag. Proper motions of most TGAS stars are improved over their Gaia data and the precision level of TGAS proper motions is extended to many millions more, fainter stars. External comparisons were made using stellar cluster fields and extragalactic sources. The TGAS data allow us to derive the limiting precision of the UCAC x,y data, which is significantly better than 1/100 pixel. A mirror of UCAC5 exists in the MAST holdings and is thus available as a cone search. All available catalogs are listed at http://archive.stsci.edu/vo/mast_services.html.