Most computational approaches makes the assumption that each MS/MS spectrum comes from one peptide while there are numerous situations where one MS/MS spectrum can contain fragment ions corresponding to two or more peptides. Examples include mixture spectra from co-eluting peptides in complex samples, spectra generated from data-independent acquisition methods and spectra from peptides with complex PTMs and cross-linked peptides. We propose a new database search tool (MixDB) that is able to identify mixture MS/MS spectra from more than one peptide. We show that peptides can be reliably identified with up to 95% accuracy from mixture spectra while considering only a small fraction of all possible peptide pairs (speedup of four orders of magnitude).