We study lattice constructions of gapped fermionic phases of matter. We show that the construction of fermionic Symmetry Protected Topological orders by Gu and Wen has a hidden dependence on a discrete spin structure on the Euclidean space-time. The spin structure is needed to resolve ambiguities which are otherwise present. An identical ambiguity is shown to arise in the fermionic analog of the string-net construction of 2D topological orders. We argue that the need for a spin structure is a general feature of lattice models with local fermionic degrees of freedom and is a lattice analog of the spin-statistics relation.