Quantum materials are notoriously sensitive to their environments, where small perturbations can tip a system toward one of several competing ground states. Graphene hosts a rich assortment of such competing phases, including a bond density wave instability ("Kekulé distortion") that couples electrons at the K/K' valleys and breaks the lattice symmetry. Here, we report observations of a ubiquitous Kekulé distortion across multiple graphene systems. We show that extremely dilute concentrations of surface atoms (less than three adsorbed atoms every 1000 graphene unit cells) can self-assemble and trigger the onset of a global Kekulé density wave phase. Combining complementary momentum-sensitive angle-resolved photoemission spectroscopy (ARPES) and low-energy electron diffraction (LEED) measurements, we confirm the presence of this density wave phase and observe the opening of an energy gap. Our results reveal an unexpected sensitivity of the graphene lattice to dilute surface disorder and show that adsorbed atoms offer an attractive route toward designing novel phases in two-dimensional materials.