We present the first full catalog and science results for the NuSTAR serendipitous survey. The catalog incorporates data taken during the first 40 months of NuSTAR operation, which provide ~20Ms of effective exposure time over 331 fields, with an areal coverage of 13 sq deg, and 497 sources detected in total over the 3-24 keV energy range. There are 276 sources with spectroscopic redshifts and classifications, largely resulting from our extensive campaign of ground-based spectroscopic followup. We characterize the overall sample in terms of the X-ray, optical, and infrared source properties. The sample is primarily comprised of active galactic nuclei (AGNs), detected over a large range in redshift from z = 0.002 - 3.4 (median of <z> = 0.56), but also includes 16 spectroscopically confirmed Galactic sources. There is a large range in X-ray flux, from log( f_3-24keV / erg s^-1 cm^-2 ) ~ -14 to -11, and in rest-frame 10-40 keV luminosity, from log( L_10-40keV / erg s^-1 ) ~ 39 to 46, with a median of 44.1. Approximately 79% of the NuSTAR sources have lower energy (<10 keV) X-ray counterparts from XMM-Newton, Chandra, and Swift/XRT. The mid-infrared (MIR) analysis, using WISE all-sky survey data, shows that MIR AGN color selections miss a large fraction of the NuSTAR-selected AGN population, from ~15% at the highest luminosities (Lx > 10^44 erg s^-1) to ~80% at the lowest luminosities (Lx < 10^43 erg s^-1). Our optical spectroscopic analysis finds that the observed fraction of optically obscured AGNs (i.e., the Type 2 fraction) is F_Type2 = 53(+14-15)%, for a well-defined subset of the 8-24 keV selected sample. This is higher, albeit at a low significance level, than the Type 2 fraction measured for redshift- and luminosity-matched AGNs selected by <10 keV X-ray missions.