Summary: We consider the nonlinear Schrödinger equation \[ (-\Delta +V(x))u = \Gamma(x) |u|^{p-1}u, \quad x\in {\mathbb R}^n \] with \(V(x) = V _{1}(x)\), \(\Gamma (x) = \Gamma _{1}(x)\) for \(x _{1} > 0\) and \(V(x) = V _{2}(x)\), \(\Gamma (x) = \Gamma _{2}(x)\) for \(x _{1} < 0\), where \(V _{1}\), \(V _{2}\), \(\Gamma _{1}\), \(\Gamma _{2}\) are periodic in each coordinate direction. This problem describes the interface of two periodic media, e.g. photonic crystals. We study the existence of ground state \(H ^{1}\) solutions (surface gap soliton ground states) for \(0 < \text{min}\, \sigma(- \Delta + V)\). Using a concentration compactness argument, we provide an abstract criterion for the existence based on ground state energies of each periodic problem (with \(V \equiv V _{1}\), \(\Gamma \equiv \Gamma _{1}\) and \(V \equiv V _{2}\), \(\Gamma \equiv \Gamma _{2}\)) as well as a more practical criterion based on ground states themselves. Examples of interfaces satisfying these criteria are provided. In 1D it is shown that, surprisingly, the criteria can be reduced to conditions on the linear Bloch waves of the operators \({-\tfrac{d^2}{dx^2} +V_1(x)}\) and \({-\tfrac{d^2}{dx^2} +V_2(x)}\).