Cell division, endocytosis, and viral budding would not function without the localization and assembly of protein complexes on membranes. What is poorly appreciated, however, is that by localizing to membranes, proteins search in a reduced space that effectively drives up concentration. Here we derive an accurate and practical analytical theory to quantify the significance of this dimensionality reduction in regulating protein assembly on membranes. We define a simple metric, an effective equilibrium constant, that allows for quantitative comparison of protein-protein interactions with and without membrane present. To test the importance of membrane localization for driving protein assembly, we collected the protein-protein and protein-lipid affinities, protein and lipid concentrations, and volume-to-surface-area ratios for 46 interactions between 37 membrane-targeting proteins in human and yeast cells. We find that many of the protein-protein interactions between pairs of proteins involved in clathrin-mediated endocytosis in human and yeast cells can experience enormous increases in effective protein-protein affinity (10-1000 fold) due to membrane localization. Localization of binding partners thus triggers robust protein complexation, suggesting that it can play an important role in controlling the timing of endocytic protein coat formation. Our analysis shows that several other proteins involved in membrane remodeling at various organelles have similar potential to exploit localization. The theory highlights the master role of phosphoinositide lipid concentration, the volume-to-surface-area ratio, and the ratio of 3D to 2D equilibrium constants in triggering (or preventing) constitutive assembly on membranes. Our simple model provides a novel quantitative framework for interpreting or designing in vitro experiments of protein complexation influenced by membrane binding.