We introduce a new Bayesian HI spectral line fitting technique capable of obtaining spectroscopic redshifts for millions of galaxies in radio surveys with the Square Kilometere Array (SKA). This technique is especially well-suited to the low signal-to-noise regime that the redshifted 21-cm HI emission line is expected to be observed in, especially with SKA Phase 1, allowing for robust source detection. After selecting a set of continuum objects relevant to large, cosmological-scale surveys with the first phase of the SKA dish array (SKA1-MID), we simulate data corresponding to their HI line emission as observed by the same telescope. We then use the MultiNest nested sampling code to find the best-fitting parametrised line profile, providing us with a full joint posterior probability distribution for the galaxy properties, including redshift. This provides high quality redshifts, with redshift errors $Delta z / z <10^{-5}$, from radio data alone for some 1.8 million galaxies in a representative 5000 square degree survey with the SKA1-MID instrument with up-to-date sensitivity profiles. Interestingly, we find that the SNR definition commonly used in forecast papers does not correlate well with the actual detectability of an HI line using our method. We further detail how our method could be improved with per-object priors and how it may be also used to give robust constraints on other observables such as the HI mass function. We also make our line fitting code publicly available for application to other data sets.