The comprehensive assignment of individual resonances of the nuclear magnetic resonance spectrum of a protein to specific atoms remains a labor-intensive and often debilitating task -especially for proteins larger than 30 kDa. Recently, there have been tremendous advances in our empirical knowledge of the relationship between the structural context of a nuclear spin and its observed resonance frequency. Indeed, the expansion in the database of determined high-resolution protein structures and recent advances in structure prediction provide an enormous resource in this respect. Robust automation of the resonance assignment process nevertheless often remains a bottleneck in the exploitation of solution NMR spectroscopy for the study of protein structure-dynamics-function relationships. Here we present a new approach for the assignment of backbone triple resonance spectra of proteins. A Bayesian statistical analysis of predicted and observed chemical shifts is used to provide a pseudo-energy potential to drive the search for the most optimal set of resonance assignments. This approach has been implemented in the C++ program Bayllagio and tested against protein systems ranging in size to over 450 amino acids. Bayllagio makes almost no errors, accommodates incomplete information, is sufficiently fast to allow for real-time evaluation of data acquisition, and greatly outperforms currently employed deterministic algorithms.