Gaussian processes are a flexible framework for quantifying uncertainty and for sequential decision-making but are limited by the requirement of solving linear systems. In general, this has a cubic cost in dataset size and is sensitive to conditioning. We explore stochastic gradient algorithms as a computationally efficient method of approximately solving these linear systems. Experimentally, stochastic gradient descent achieves state-of-the-art performance on large-scale regression tasks. Its uncertainty estimates match the performance of significantly more expensive baselines on a large-scale Bayesian optimization task. On a molecular binding affinity prediction task, our method places Gaussian processes with a Tanimoto kernel on par with state-of-the-art graph neural networks.