Proteins need to selectively interact with specific targets among a multitude of similar molecules in the cell. Despite a physical understanding of pairwise binding interactions, we lack a general theory of how proteins evolve high specificity. Here, we present a genetic, mechano-chemical model of evolving protein-ligand interactions which offers a mechanistic understanding of molecular discrimination: There are many routes to achieving discrimination – varying degrees of flexibility and shape/chemistry complementarity – but the key ingredient is precision. Harder discrimination tasks require more collective and precise interplay of structure, forces and dynamics. Proteins can achieve this through correlated mutations extending far from a binding site, which fine tune the localized interaction with the ligand. Thus, the solution of more complicated tasks requires larger proteins, and proteins become more evolvable and robust when they are larger than the bare minimum required for discrimination. Our model makes testable, specific predictions about the role of flexibility in discrimination, how to independently tune affinity and specificity. Thus, the proposed theory of molecular discrimination sheds light on a question that is often taken for granted – “why are proteins so big?” One possible answer is, “because molecular discrimination is often a hard task.”