Although direct fragmentation of protein ions in a mass spectrometer is far more efficient than exhaustive mapping of 1-3 kDa peptides for complete characterization of primary structures predicted from sequenced genomes, the development of this approach is still in its infancy. Here we describe a statistical model (good to within approximately 5%) that shows that the database search specificity of this method requires only three of four fragment ions to match (at +/-0.1 Da) for a 99.8% probability of being correct in a database of 5,000 protein forms. Software developed for automated processing of protein ion fragmentation data and for probability-based retrieval of whole proteins is illustrated by identification of 18 archaeal and bacterial proteins with simultaneous mass-spectrometric (MS) mapping of their entire primary structures. Dissociation of two or three proteins at once for such identifications in parallel is also demonstrated, along with retention and exact localization of a phosphorylated serine residue through the fragmentation process. These conceptual and technical advances should assist future processing of whole proteins in a higher throughput format for more robust detection of co- and post-translational modifications.