Recent work has shown that the star formation-density relation -- in which galaxies with low star formation rates are preferentially found in dense environments -- is still in place at z~1, but the situation becomes less clear at higher redshifts. We use mass-selected samples drawn from the UKIDSS Ultra-Deep Survey to show that galaxies with quenched star formation tend to reside in dense environments out to at least z~1.8. Over most of this redshift range we are able to demonstrate that this star formation-density relation holds even at fixed stellar mass. The environmental quenching of star formation appears to operate with similar efficiency on all galaxies regardless of stellar mass. Nevertheless, the environment plays a greater role in the build-up of the red sequence at lower masses, whereas other quenching processes dominate at higher masses. In addition to a statistical analysis of environmental densities, we investigate a cluster at z=1.6, and show that the central region has an elevated fraction of quiescent objects relative to the field. Although the uncertainties are large, the environmental quenching efficiency in this cluster is consistent with that of galaxy groups and clusters at z~0. In this work we rely on photometric redshifts, and describe some of the pitfalls that large redshift errors can present.