We describe the number counts and spatial distribution of 239 distant red galaxies (DRGs), selected from the Early Data Release of the UKIDSS Ultra Deep Survey. The DRGs are identified by their very red infrared colours with (J - K)AB > 1.3, selected over 0.62 deg2 to a 90 per cent completeness limit of KAB ~= 20.7. This is the first time that a large sample of bright DRGs has been studied within a contiguous area, and we provide the first measurements of their number counts and clustering. The population shows strong angular clustering, intermediate between those of K-selected field galaxies and optical/infrared-selected extremely red galaxies. Adopting the redshift distributions determined from other recent studies, we infer a high correlation length of r0 ~11h-1Mpc. Such strong clustering could imply that our galaxies are hosted by very massive dark matter haloes, consistent with the progenitors of present-day L >~ L* elliptical galaxies.