Geometrically frustrated magnets typically consist of either triangular or tetrahedral blocks of magnetic ions. A novel frustrated motif is provided by octahedral blocks. Magnetic ions form a corner-sharing network of octahedra in antiperovskites and Mn₃X intermetallics, whereas edge-shared octahedra emerge for the J₁–J₂ spin model on a face-centered cubic (fcc) lattice for a special ratio of two exchanges J₂/J₁ = 0.5. We illustrate an emergent complex behavior of octahedral antiferromagnets by studying the magnetization process of the classical J₁–J₂ fcc antiferromagnet. Up to eight different phases exist in magnetic field including two fractional magnetization plateaus at M/M_sat = 1/3 and 2/3. An unusual twist in the quantum order-by-disorder effect due to magnon-magnon interactions is also found for the nearest-neighbor fcc antiferromagnet in zero field.