A cryogenic apparatus is described that enables a new experiment, nEDM@SNS, with a major improvement in sensitivity compared to the existing limit in the search for a neutron Electric Dipole Moment (EDM). It uses superfluid $^4$He to produce a high density of Ultra-Cold Neutrons (UCN) which are contained in a suitably coated pair of measurement cells. The experiment, to be operated at the Spallation Neutron Source at Oak Ridge National Laboratory, uses polarized $^3$He from an Atomic Beam Source injected into the superfluid $^4$He and transported to the measurement cells as a co-magnetometer. The superfluid $^4$He is also used as an insulating medium allowing significantly higher electric fields, compared to previous experiments, to be maintained across the measurement cells. These features provide an ultimate statistical uncertainty for the EDM of $2-3times 10^{-28}$ e-cm, with anticipated systematic uncertainties below this level.