Ab initio G2M(MP2) calculations show the BeO + CH4 reaction to proceed by barrier-less formation of the CH4BeO complex bound by 20.7 kcal/mol followed by isomerization to a CH3BeOH molecule (87.8 kcal/mol below BeO + CH4). CH3BeOH can dissociate without an exit barrier to BeOH + CH3 (0.5 kcal/mol below the reactants) or rearrange through a high barrier (25.7 kcal/mol. above BeO + CH4) to a weakly bound CH3OHBe complex. Direct hydrogen abstraction from methane leading to BeOH and CH3 may be also feasible. The calculations demonstrate BeO as a useful catalyst at the initial stage of the conversion of methane to important organic compounds.