The results of an exploratory lattice study of heavy baryon spectroscopy are presented. We have computed the full spectrum of the eight baryons containing a single heavy quark, on a 24(3) X 48 lattice at beta=6.2, using an O(a)-improved fermion action. We discuss the lattice baryon operators and give a method for isolating the contributions of the spin doublets (Sigma,Sigma*), (Xi',Xi*), and (Omega,Omega) to the correlation function of the relevant operator. We compare our results with the available experimental data and find good agreement in both the charm and the b-quark sectors, despite the long extrapolation in the heavy quark mass needed in the latter case. We also predict the masses of several undiscovered baryons. We compute the Lambda-pseudoscalar meson and Sigma-Lambda mass splittings. Our results, which have errors in the range 10-30%, are in good agreement with the experimental numbers. For the Sigma*-Sigma mass splitting, we find results considerably smaller than the experimental values for both the charm and the b-flavored baryons, although in the latter case the experimental results are still preliminary. This is also the case for the lattice results for the hyperfine splitting for the heavy mesons.