Determination of gem provenance is a topic of research in the gemological community for financial, security, and societal reasons. Laser-induced breakdown spectroscopy (LIBS) and multivariate analysis have the potential to revolutionize the field of gem provenance. This study acquired LIBS spectra from 569 rough sapphire and ruby specimens from 21 localities in 11 countries. The spectra were analyzed using the multivariate technique partial least-squares regression (PLSR) in separate algorithms for sapphires and rubies. Each algorithm consists of a series of PLS models. Each model compares the spectra from a locality of interest to the spectra from all other localities in the database. Success rates, as determined by the percent of correct provenance identifications, are 98.9% (sapphire) and 96.0% (ruby) for country of origin and 97.9% (sapphire) and 95.4% (ruby) for deposit of origin. Individual deposits are not recognized by the concentrations of a few elements; rather, the unique compositional signature of each deposit consists of the ratios of many elements, primarily Ca, Zr, Fe, Ba, Mt, Ti, Sr, Si, Cr, H, C, and Li, some of which may reside in inclusions. This work demonstrates that determination of country or deposit of origin may be related to a quantitative measure with a high level of success.