Orthogonal spin ordering is rarely observed in magnetic oxides because nearest-neighbor symmetric Heisenberg superexchange interactions usually dominate. We have discovered that in the quadruple perovskite CaFe3Ti4O12, where only the S=2 Fe2+ ion is magnetic, long-range magnetic order consisting of an unusual arrangement of three interpenetrating orthogonal sublattices is stabilized. Each magnetic sublattice corresponds to a set of FeO4 square planes sharing a common orientation. This multi-k magnetic spin ordering is the result of fourth-neighbor spin couplings with a strong easy-axis anisotropy. In an applied magnetic field, each sublattice tends towards ferromagnetic alignment, but remains polarized by internal magnetic fields generated by the others, thus stabilizing in a noncollinear canted ferromagnetic structure. CaFe3Ti4O12 provides a rare example of how nontrivial long-range spin order can arise when near-neighbor Heisenberg superexchange is quenched.