We address the existence of traveling single-humped localized solutions in the spatially discrete nonlinear Schrodinger (NLS) equation. A mathematical technique is developed for analysis of persistence of these solutions from a certain limit in which the dispersion relation of linear waves contains a triple zero. The technique is based on using the Implicit Function Theorem for solution of an appropriate differential advance-delay equation in exponentially weighted spaces. The resulting Melnikov calculation relies on a number of assumptions on the spectrum of the linearization around the pulse, which are checked numerically. We apply the technique to the so-called Salerno model and the translationally invariant discrete NLS equation with a cubic nonlinearity. We show that the traveling solutions terminate in the Salerno model whereas they generally persist in the translationally invariant NLS lattice as a one-parameter family of solutions. These results are found to be in a close correspondence with numerical approximations of traveling solutions with zero radiation tails. Analysis of persistence also predicts the spectral stability of the one-parameter family of traveling solutions under time evolution of the discrete NLS equation. (C) 2007 Elsevier B.V. All rights reserved.