Accurate detection of neuropeptides in the tandem mass spectrometry experiments using database search programs remains an area of active research. Of interest is accurate computation of statistical significance levels assigned to observed-theoretical spectrum matches. Main factors that influence significance values are peptide size, incomplete fragmentation, low spectra quality, and density of the database search space. A Monte Carlo approach was used to generate k-permuted decoy databases that would offer accurate p-values calculations in the database search program Crux. The k-permuted decoy databases were generated from 236 peptides that fall within 12 Daltons of the masses of 80 SwePep tandem spectra in a target database of 618 neuropeptides. The performance of the kpermuted decoy databases to identify peptides was examined relative to the approach already implemented in the Crux. The ability of the Crux's indicators of peptide match: number of matched fragment ions, XCorr and Sp score to identify peptides was compared using permutation p-values. The proposed method improved the detection of neuropeptides relative to the approach implemented in Crux. The performance of the number of matched fragment ions and Sp score was comparable and both indicators detected 98.75 and 100.0% of the peptides using 105 and 106 whole sequence k-permuted decoy databases, respectively. The XCorr indicator had the weakest performance relative to the other indicators. The proposed approach can be integrated with multiple database search programs and other types of tandem mass spectrometry experiments.