Nanostructuring metal catalysts has been demonstrated as an attractive strategy to enable selective hydrodehalogenation of CH₂X₂ (X = Cl, Br) to CH₃X, but active phase size effects of promising metals and the role of the halogen are still poorly understood. Herein, the impact of these parameters on performance (activity, selectivity, and stability) is systematically assessed by employing a platform of N–doped carbon–supported metal nanostructures (Ir, Pt, Ru, and Ni), ranging from single atoms (SA) with defined coordination environment to nanoparticles (NP) of ca. 3.0 nm. Catalytic tests reveal that when compared to single atoms, highest reaction rates are attained over NP–based systems, which also exhibit improved stability ranking as Ir ≈ Pt > Ru ≫ Ni, independent of the halogen. The product distribution was markedly affected by the nanostructure and speciation of the active center as well as the dihalomethane type. Specifically, CH₃Cl is the main reaction product over SA in hydrodechlorination, achieving an exceptional selectivity over Ir (up to 95%). In contrast, NP mainly generated CH₄ or coke. Comparable patterns were observed in hydrodebromination, except over Ru, which exhibited an inverse structure–selectivity trend. Density Functional Theory simulations shed light on the speciation of the active phase and identified the adsorption and dissociation energies of CH₂X₂ and H₂ as descriptors for catalytic reactivity. These findings elucidate hydrodehalogenation performance patterns, highlighting the impact of nanostructuring and the halogen type to advance future catalyst design.