We present initial results and the source catalog from the NuSTAR survey of the Extended Chandra Deep Field South (hereafter, ECDFS) - currently the deepest contiguous component of the NuSTAR extragalactic survey program. The survey covers the full ~30 arcmin x 30 arcmin area of this field to a maximum depth of ~360 ks (~220 ks when corrected for vignetting at 3-24 keV), reaching sensitivity limits of ~1.3 x 10^-14 erg/cm2/s (3-8 keV), ~3.4 x 10^-14 erg/cm2/s (8-24 keV) and ~3.0 x 10^-14 erg/cm2/s (3-24 keV). Fifty four (54) sources are detected over the full field, although five of these are found to lie below our significance threshold once contaminating flux from neighboring (i.e., blended) sources is taken into account. Of the remaining 49 that are significant, 19 are detected in the 8-24 keV band. The 8-24 keV to 3-8 keV band ratios of the twelve sources that are detected in both bands span the range 0.39-1.7, corresponding to a photon index range of Gamma ~ 0.5-2.3, with a median photon index of 1.70 +/- 0.52. The redshifts of the 49 sources in our main sample span the range z = 0.21-2.7, and their rest-frame 10-40 keV luminosities (derived from the observed 8-24 keV fluxes) span the range L(10-40 keV) ~ (0.7-300) x 10^43 erg/s, sampling below the knee of the X-ray luminosity function out to z ~ 0.8-1. Finally, we identify one NuSTAR source that has neither a Chandra nor an XMM-Newton counterpart, but that shows evidence of nuclear activity at infrared wavelengths, and thus may represent a genuine, new X-ray source detected by NuSTAR in the ECDFS.