Heterostructured photocatalysts comprised of microcrystalline (mc-) cores and nanostructured (ns-) shells were prepared by the sol-gel method. The ability of titania-coated ATiO3 (A = Fe, Pb) and AFeO3 (A = Bi, La, Y) catalysts to degrade methylene blue in visible light (λ > 420 nm) was compared. The catalysts with the titanate cores had enhanced photocatalytic activities for methylene blue degradation compared to their components alone, whereas the catalysts with ferrite cores did not. The temperature at which the ns-titania shell is crystallized influences the photocatalytic dye degradation. mc-FeTiO3/ns-TiO2 annealed at 500 °C shows the highest reaction rate. Fe-doped TiO2, which absorbs visible light, did not show enhanced photocatalytic activity for methylene blue degradation. This result indicates that iron contamination is not a decisive factor in the reduced reactivity of the titania coated ferrite catalysts. The higher reactivity of materials with the titanate cores suggests that photogenerated charge carriers are more easily transported across the titanate-titanate interface than the ferrite-titanate interface and this provides guidance for materials selection in composite catalyst design.