We have carried out a hybrid density functional study of mechanisms for oxidative dehydrogenation of propane on the (010) surface of V2O5. The surface was modeled using both vanadium oxide clusters and a periodic slab. We have investigated a Mars-van Krevelen mechanism that involves stepwise adsorption of the propane at an oxygen site followed by desorption of a water molecule and propene, and subsequent adsorption of an oxygen molecule to complete the catalytic cycle. The potential energy surface is found to have large barriers, which are lowered somewhat when the possibility of a triplet state is considered. The barriers for propane adsorption and propene elimination are 45-60 kcal/mol. The highest energy on the potential energy Surface at the B3LYP/6-31G(*) level of theory is about 80 kcal/mol above the energy of the reactants and corresponds to formation of an oxygen vacancy after water elimination. Subsequent addition of an oxygen molecule to fill the vacancy is predicted to be energetically downhill. The reactions of propane at a bridging oxygen site and at a vanadyl site have similar energetics. The key results of the cluster calculations are confirmed by periodic calculations. Factors that may lower the barriers on the potential energy surface, including, the interaction of vanadium oxide clusters with a support material and a concerted reaction with O-2, are discussed.