We present a catalog of 4880 newly identified RR Lyrae variable stars (4433 RRab, 446 RRc and 1 RRd) found during the search for supernovae by the All-Sky Automated Survey for Supernovae (ASAS-SN). The light curves, classified using the "Upsilon" random forest classifier and visually verified, are available through the ASAS-SN variable star database (https://asas-sn.osu.edu/variables). The database also contains light curves for an expanding number of additional new variables (~50,000 at present) and will begin to include the light curves of known variable stars in the near future.