We show that unconventional spin order arises naturally in two-component dipolar Fermi gases of atoms or molecules, which recently became accessible experimentally, in optical lattices. Using an unbiased functional renormalization-group analysis, we find that dipolar interactions lead to an instability of the gas toward an l = 1 spin-density wave state. This phase is the particle-hole analog of spin-triplet, p-wave Cooper pairs. The order parameter for such spin-density waves of p-wave orbital symmetry is a vector in spin space and, moreover, is defined on lattice bonds rather than on lattice sites. We determine the rich quantum phase diagram of dipolar fermions at half filling on the square lattice as a function of the dipolar orientation and discuss how these exotic spin-density waves emerge amidst competition with superfluid and charge-density wave phases. DOI: 10.1103/PhysRevA.87.043604