We have theoretically studied the oxidative addition of all halomethanes CH3X (with X = F, Cl, Br, I, At) to Pd and PdCl-, using both nonrelativistic and zeroth-order-regular-approximation-relativistic density functional theory at BLYP/QZ4P. Our study covers the gas phase as well as the condensed phase (water), where solvent effects are described with the conductor-like screening model. The activation of the C−X bond may proceed via two stereochemically different pathways:  (i) direct oxidative insertion (OxIn) which goes with retention of the configuration at C and (ii) an alternative SN2 pathway which goes with inversion of the configuration at C*. In the gas phase, for Pd, the OxIn pathway has the lowest reaction barrier for all CH3X's. Anion assistance, that is, going from Pd to PdCl-, changes the preference for all CH3X's from OxIn to the SN2 pathway. Gas-phase reaction barriers for both pathways to C−X activation generally decrease as X descends in group 17. Two striking solvent effects are (i) the shift in reactivity of Pd + CH3X from OxIn to SN2 in the case of the smaller halogens, F and Cl, and (ii) the shift in reactivity of PdCl- + CH3X in the opposite direction, that is, from SN2 to OxIn, in the case of the heavier halogens, I and At. We use the activation strain model to arrive at a qualitative understanding of how the competition between OxIn and SN2 pathways is determined by the halogen atom in the activated C−X bond, by anion assistance, and by solvation.