Identification of the individual chemical constituents of a mixture, especially solutions extracted from medicinal plants, is a time-consuming task. The identification results are often limited by challenges such as the development of separation methods and the availability of known reference standards. A novel structure elucidation system, NP-StructurePredictor, is presented and used to accelerate the process of identifying chemical structures in a mixture based on a branch and bound algorithm combined with a large collection of natural product databases. NP-StructurePredictor requires only targeted molecular weights calculated from a list of m/z values from liquid chromatography-mass spectrometry (LC-MS) experiments as input information to predict the chemical structures of individual components matching the weights in a mixture. NP-StructurePredictor also provides the predicted structures with statistically calculated probabilities so that the most likely chemical structures of the natural products and their analogs can be proposed accordingly. Four data sets consisting of different Chinese herbs with mixtures containing known compounds were selected for validation studies, and all their components were correctly identified and highly predicted using NP-StructurePredictor. NP-StructurePredictor demonstrated its applicability for predicting the chemical structures of novel compounds by returning highly accurate results from four different validation case studies.