  We present the results of a deep K_s-band (2.1 um) imaging survey of the
Spitzer/HETDEX Exploratory Large Area (SHELA) field using the NEWFIRM
near-infrared (NIR) camera on the KPNO Mayall 4-m telescope. This NEWFIRM
HETDEX Survey (NHS) reaches a 5-sigma depth of 22.4 AB mag (2"-diameter
apertures corrected to total), is ~50% and 90% complete at K~22.65 and K~22.15,
respectively, and covers 22 deg^2 of the 24 deg^2 SHELA Spitzer/ IRAC footprint
(within ``Stripe 82' of the Sloan Digital Sky Survey). We present a
K_s-band-selected catalog which includes deep ugriz imaging from the Dark
Energy Camera and 3.6 and 4.5 um imaging from Spitzer/IRAC, with
forced-photometry of 1.7 million sources across 17.5 deg^2. The large area and
moderate depth of this catalog enables the study of the most massive galaxies
at high redshift, and minimizes uncertainties associated with counting
statistics and cosmic variance. As a demonstration, we derive stellar masses
(M*) and star-formation rates (SFRs) for candidate galaxies at 3 < z < 5, and
select a conservative sample of nine candidate massive (M* > 10^11 Msol)
quiescent galaxies, which have measured SFRs significantly below the
main-sequence at this redshift. Five are ultra-massive with M* > 10^12, though
uncertainties in IRAC blending, gravitational lensing, or AGN emission could
result in true masses which are lower. Simulations predict that these galaxies
should be extremely rare, thus we discuss what physical processes in models
could be altered to allow the formation of such massive quiescent galaxies at
such early times.
