We present a comprehensive model for the nucleation of domains in membrane adhesion. We determine the critical number of bonds in a nucleus and calculate the probability distribution of nucleation time from a discrete master equation. The latter is characterized by only four effective rates, which account for cooperative effects between bonds. We validate our model by finding excellent agreement with extensive Langevin simulations. In the range of parameters typical for cell adhesion, we find the critical number of bonds to be small. Furthermore, we find a characteristic separation between the bonds at which nucleation is particularly fast, pointing to potential regulatory mechanisms that could be used to control the cell recognition processes.