Fulde, Ferrell, Larkin, and Ovchinnikov (FFLO) predicted inhomogeneous superconducting and superfluid ground states, spontaneously breaking translation symmetries. In this Letter, we demonstrate that the transition from the FFLO to the normal state as a function of temperature or increased Fermi surface splitting is not a direct one. Instead the system has an additional phase transition to a different state where pair-density-wave superconductivity (or superfluidity) exists only on the boundaries of the system, while the bulk of the system is normal. The surface pair-density-wave state is very robust and exists for much larger fields and temperatures than the FFLO state.