We have used in situ X-ray diffraction and line profile analysis to study the carburization of a 6 nm Pd catalyst supported on carbon at various temperatures under helium, hydrogen, and oxygen. A maximum of 10% C atoms was dissolved in the Pd lattice. This phase is stable at ambient conditions but decays above 400 degrees C. The rate of formation is limited by active C from the support and is slower by a factor of similar to 100 compared to the supply of C atoms via CO decomposition. The bulk diffusion coefficient predicts an even faster rate, demanding a surface barrier to activate bulk diffusion. We find that the rate of formation depends on the surface to volume ratio. Carbon is nonuniformly distributed among individual Pd particles, but hydrogen fills interstitial sites to lift the irregularity. In the ternary phase PdC(x)H(y), x and y are linearly linked. Oxygen reacts with interstitial carbon already below 160 degrees C.