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 error in the electronic structure methods. We also extend the recently-developed ShiftML machine-learning model, including the evaluation of the uncertainty of its predictions. 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 of 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 $^{13}$C shifts are underestimated, and that more accurate, self-consistently determined uncertainties make it possible to use $^{13}$C shifts to improve the accuracy of structure determinations.