How cells polarize in response to external cues is a fundamental biological problem. For mating, yeast cells orient growth toward the source of a pheromone gradient produced by cells of the opposite mating type [1, 2]. Polarized growth depends on the small GTPase Cdc42, a central eukaryotic polarity regulator that controls signaling, cytoskeleton polarization, and vesicle trafficking [3]. However, the mechanisms of polarity establishment and mate selection in complex cellular environments are poorly understood. Here we show that, in fission yeast, low-level pheromone signaling promotes a novel polarization state, where active Cdc42, its GEF Scd1, and scaffold Scd2 form colocalizing dynamic zones that sample the periphery of the cell. Two direct Cdc42 effectors—actin cables marked by myosin V Myo52 and the exocyst complex labeled by Sec6 and Sec8—also dynamically colocalize with active Cdc42. However, these cells do not grow due to a block in the exocytosis of cell wall synthases Bgs1 and Bgs4. High-level pheromone stabilizes active Cdc42 zones and promotes cell wall synthase exocytosis and polarized growth. However, in the absence of prior low-level pheromone signaling, exploration fails, and cells polarize growth at cell poles by default. Consequently, these cells show altered partner choice, mating preferentially with sister rather than nonsister cells. Thus, Cdc42 exploration serves to orient growth for partner selection. This process may also promote genetic diversification.