To investigate the nature and role of cell adhesion in plants, we analyzed the initial step of pollination in Arabidopsis: the binding of pollen grains to female stigma cells. Here we show this interaction occurs within seconds of pollination. Because it takes place prior to pollen hydration, it also requires adhesion molecules that can act in a virtually dry environment. We developed assays that monitored adhesion of populations of pollen grains and individual cells. Adhesion between pollen and stigma cells is highly selective - Arabidopsis pollen binds with high affinity to Arabidopsis stigmas, while pollen from other species fails to adhere. Initial binding is independent of the extracellular pollen coat (tryphine), indicating that adhesion molecules reside elsewhere on the pollen surface, most likely within the exine walls. Immediately after pollination, the stigma surface becomes altered at the interface, acquiring a pattern that interlocks with the exine; this pattern is evident only with pollen from Arabidopsis and its close relatives. Purified exine fragments bind to stigma cells, and biochemical analyses indicate that this specific, rapid and anhydrous adhesion event is mediated by lipophilic interactions.