The study of superfluid fermion pairs in a periodic potential has important ramifications for understanding superconductivity in crystalline materials. Using cold atomic gases, various condensed matter models can be studied in a highly controllable environment. Weakly repulsive fermions in an optical lattice could undergo d-wave pairing at low temperatures, a possible mechanism for high temperature superconductivity in the cuprates. The lattice potential could also strongly increase the critical temperature for s-wave superfluidity. Recent experimental advances in the bulk include the observation of fermion pair condensates and high-temperature superfluidity. Experiments with fermions and bosonic bound pairs in optical lattices have been reported, but have not yet addressed superfluid behavior. 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, a property of a superfluid. Conceptually, this implies that strong s-wave pairing and superfluidity have now been established in a lattice potential, where the transport of atoms occurs by quantum mechanical tunneling and not by simple propagation. 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, possibly due to a superfluid to insulator transition. Such strongly interacting fermions in an optical lattice can be used to study a new class of Hamiltonians with interband and atom-molecule couplings.