Recently, we introduced a novel proteomics method employing a metalloendopeptidase with Lys-N specificity to produce proteolytic peptides. Fragmentation spectra generated by electron transfer dissociation, for a large proportion of the Lys-N proteolytic peptides, were found to be dominated by extensive series of c-type ions. Taking advantage of this unique spectral property, we developed an algorithm, LysNDeNovo, to facilitate de novo sequencing of these peptides. LysNDeNovo contains simple and naive heuristics to demonstrate a proof of concept, i.e. that Lys-N peptide electron transfer dissociation spectra are perfectly suited for de novo interpretation. A stringent "golden" dataset of peptides identified by conventional database search algorithms was taken to validate the performance of LysNDeNovo. The results on this dataset indicate that LysNDeNovo was able to confidently identify a considerable proportion (42%), without requiring any prior genome or protein sequences. Results of similar quantity and quality could also be obtained on a much more extensive experimental dataset, illustrating the potential for higher throughput de novo sequencing using these methods.