The identification of the active sites and the derivation of structure-performance relationships are central for the development of high-performance heterogeneous catalysts. Here, a platform of platinum nanostructures, ranging from single atoms to nanoparticles of ≈4 nm supported on activated- and N-doped carbon (AC and NC), is employed to systematically assess nuclearity and host effects on the activity, selectivity, and stability in dibromomethane hydrodebromination, a key step in bromine-mediated methane functionalization processes. For this purpose, catalytic evaluation is coupled to in-depth characterization, kinetic analysis, and mechanistic studies based on density functional theory. Remarkably, the single atom catalysts achieve exceptional selectivity toward CH3Br (up to 98%) when compared to nanoparticles and any previously reported system. Furthermore, the results reveal unparalleled specific activity over 1.3–2.3 nm-sized platinum nanoparticles, which also exhibit the highest stability. Additionally, host effects are found to markedly affect the catalytic performance. Specifically, on NC, the activity and CH3Br selectivity are enhanced, but significant fouling occurs. On the other hand, AC-supported platinum nanostructures deactivate due to sintering and bromination. Simulations and kinetic fingerprints demonstrate that the observed reactivity patterns are governed by the H2 dissociation abilities of the catalysts and the availability of surface H-atoms.