The study of superfluid fermion pairs in a crystalline potential has important ramifications for understanding superconductivity in many materials. By simulating such systems using cold atomic gases, various condensed matter models can be studied in a highly controllable environment. Here we show that when a condensate of fermionic atom pairs was released from an optical lattice, distinct interference peaks appear, implying long range order and superfluidity. These observations were made for unitarity limited interactions on both sides of a Feshbach resonance. For larger lattice depths, the coherence was lost in a reversible manner. Such strongly interacting fermions in an optical lattice can be used to study a new class of Hamiltonians with interband and atom-molecule couplings.