An iron molybdate/molybdenum oxide catalyst (Mo/Fe = 2) was synthesized by a hydrothermal method and the catalyst's performance and compositional changes were followed during selective oxidation of methanol to formaldehyde for up to 600 h. The activity was continuously measured for a series of experiments performed in a laboratory fixed-bed reactor with 10, 100, 250 and 600 h on stream under reaction conditions (5% MeOH, 10% O2 in N2, Temp. = 384–416 °C, W/F = 1.2 gcat h molMeOH−1). The structural and compositional changes of the catalyst were investigated by a number of techniques including: XRD, Raman spectroscopy, XPS, SEM-EDS and STEM-EDS. Methanol forms volatile species with molybdenum at reaction conditions, leading to depletion of Mo from the catalyst. Excess MoO3 was shown to volatilize and leave the catalyst during the first 10 h on stream, leading to an initial loss in activity of 50%. From 10 to 600 h on stream leaching of molybdenum from the remaining iron molybdate phase (Fe2(MoO4)3, Mo/Fe = 1.5) leads to iron rich phases (FeMoO4 and Fe2O3, Me/Fe < 1.5) and simultaneously an increase in activity to approximately 1.5 times the initial activity. Even at high degrees of molybdenum loss (Mo/Fe = 0.49) the formaldehyde selectivity remained above 92%, and the combined CO/CO2 selectivity was below 4%. This is likely due to a surface layer of MoOx on the catalyst at all times due to segregation and a surface in equilibrium with the gaseous molybdenum compounds. After 600 h on stream formation of β-MoO3 was observed, indicating that this molybdenum oxide phase is stable to some extent under reaction conditions.