Correlated, size consistent calculations have been performed for the reaction between Pd2 and CH4. Some calculations have also been done for Pd3. The results are used to interpret the experimental observations for the reactivity of palladium clusters of different sizes with CH4. The calculations indicate that the C-H bond is broken with only a small barrier of 4-6 kcal/mol and thus confirm the experimental interpretation of dissociative chemisorption. This result is in contrast to the case of N2, which was found in calculations to be only molecularly bound. There are two dominating effects for the size of the barrier in the methane reaction. The first factor is the repulsion in the entrance channel, and the other factor is the capability of strong bond formation in the product channel. For palladium clusters of different sizes these two effects compete, and this is the origin for the maximum in the curve for the reactivity versus cluster size found experimentally at about 10 atoms.