Two distinct phases, orthorhombic and hexagonal, of Mo–V–Te–O mixed oxide catalysts were prepared separately by the hydrothermal synthetic method and solid-state reaction, and these catalysts were tested for propane selective oxidation to acrylic acid. The hydrothermally synthesized orthorhombic phase of the Mo–V–Te–O catalyst showed high activity and selectivity for the oxidation of propane into acrylic acid. This catalyst also showed extremely high catalytic performance in the propene oxidation, producing acrylic acid in a high yield. The hexagonal Mo–V–Te–O catalyst was formed via the solid-state reaction between the orthorhombic Mo–V–Te–O and α-TeVO4. This phase showed poor activity to both propane and propene oxidations, although the hexagonal phase was constructed with the octahedra of Mo and V similar to the orthorhombic phase. Reaction kinetics study over the catalyst with orthorhombic structure revealed that propane oxidation was of first order with respect to propane and nearly zero order with respect to oxygen, suggesting that the rate-determining step of the reaction is C–H bond breaking of propane to form propene. Structural effects on the catalytic oxidation performance were discussed.