Magnetic n-type semiconductor Fe3O4 nanoparticle and p-type semiconductor FeWO4 nanowire heterostructures were successfully synthesized without any surfactants or templates via a facile one-step hydrothermal process at 160 °C. The heterojunction structure and morphology were characterized by X-ray powder diffraction (XRD), transmission electron microscopy (TEM) and high-resolution transmission electron microscopy (HRTEM). Magnetic measurements indicated the coexistence of ferrimagnetic behavior of Fe3O4 and weak antiferromagnetic behavior of FeWO4. The degradation of methylene blue (MB) under UV-Visible light irradiation was studied as a model experiment to evaluate the catalytic activity of the Fe3O4/FeWO4 heterostructure p-n junctions. The decomposition efficiency was 97.1% after one hour UV-Visible irradiation. This magnetic photocatalyst can be easily recovered from the solution using a permanent magnet and redispersed by removing the magnet.