We present deep near-IR (NIR) medium-bandwidth photometry over the wavelength range 1-1.8 Delta *mm in the All-wavelength Extended Groth strip International Survey (AEGIS) and Cosmic Evolution Survey (COSMOS) fields. The observations were carried out using the NOAO Extremely Wide-Field Infrared Imager (NEWFIRM) on the Mayall 4 m Telescope on Kitt Peak as part of the NEWFIRM Medium-Band Survey (NMBS), an NOAO survey program. In this paper, we describe the full details of the observations, data reduction, and photometry for the survey. We also present a public K-selected photometric catalog, along with accurate photometric redshifts. The redshifts are computed with 37 (20) filters in the COSMOS (AEGIS) fields, combining the NIR medium-bandwidth data with existing UV (Galaxy Evolution Explorer), visible and NIR (Canada-France-Hawaii Telescope and Subaru Telescope), and mid-IR (Spitzer/IRAC) imaging. We find excellent agreement with publicly available spectroscopic redshifts, with Delta *s z /(1 + z) ~ 1%-2% for ~4000 galaxies at z = 0-3. The NMBS catalogs contain ~13,000 galaxies at z > 1.5 with accurate photometric redshifts and rest-frame colors. Due to the increased spectral resolution obtained with the five NIR medium-band filters, the median 68% confidence intervals of the photometric redshifts of both quiescent and star-forming galaxies are a factor of about two times smaller when comparing catalogs with medium-band NIR photometry to NIR broadband photometry. We show evidence for a clear bimodal color distribution between quiescent and star-forming galaxies that persists to z ~ 3, a higher redshift than has been probed so far.