We describe an ab initio theory of finite temperature magnetism in strongly-correlated electron systems. The formalism is based on spin density functional theory, with a self-interaction corrected local spin density approximation (SIC-LSDA). The self-interaction correction is implemented locally, within the Kohn-Korringa-Rostoker (KKR) multiple-scattering method. Thermally induced magnetic fluctuations are treated using a mean-field 'disordered local moment' (DLM) approach and at no stage is there a fitting to an effective Heisenberg model. We apply the theory to the 3d transition metal oxides, where our calculations reproduce the experimental ordering tendencies, as well as the qualitative trend in ordering temperatures. We find a large insulating gap in the paramagnetic state which hardly changes with the onset of magnetic order.