Nuclear Magnetic Resonance (NMR) spectroscopy is particularly well suited to determine the structure of molecules and materials in powdered form. Structure determination usually proceeds by finding the best match between experimentally observed NMR chemical shifts and those of candidate structures. Chemical shifts for the candidate configurations have traditionally been computed by electronic-structure methods, and more recently predicted by machine learning. However, the reliability of the determination depends on the errors in the predicted shifts. Here we propose a Bayesian framework for determining the confidence in the identification of the experimental crystal structure, based on knowledge of the typical errors in the electronic structure methods. We demonstrate the approach on the determination of the structures of six organic molecular crystals. We critically assess the reliability of the structure determinations, facilitated by the introduction of a visualization of the similarity between candidate configurations in terms of their chemical shifts and their structures. We also show that the commonly used values for the errors in calculated 13C shifts are underestimated, and that more accurate, self-consistently determined uncertainties make it possible to use 13C shifts to improve the accuracy of structure determinations. Finally, we extend the recently-developed ShiftML model to render it more efficient, accurate, and, most importantly, to evaluate the uncertainties in its predictions. By quantifying the confidence in structure determinations based on ShiftML predictions we further substantiate that it provides a valid replacement for first-principles calculations in NMR crystallography.