We present a theory for the elasticity of cross-linked stiff polymer networks. Stiff polymers, unlike their flexible counterparts, are highly anisotropic elastic objects. Similar to mechanical beams, stiff polymers easily deform in bending, while they are much stiffer with respect to tensile forces ("stretching"). Unlike in previous approaches, where network elasticity is derived from the stretching mode, our theory properly accounts for the soft bending response. A self-consistent effective medium approach is used to calculate the macroscopic elastic moduli starting from a microscopic characterization of the deformation field in terms of "floppy modes"-low-energy bending excitations that retain a high degree of nonaffinity. The length scal...