We compute the three-loop four-gluon scattering amplitude in maximally supersymmetric Yang-Mills theory, including its full color dependence. Our result is the first complete computation of a non-planar four-particle scattering amplitude to three loops in four-dimensional gauge theory and consequently provides highly non-trivial data for the study of non-planar scattering amplitudes. We present the amplitude as a Laurent expansion in the dimensional regulator to finite order, with coefficients composed of harmonic poly-logarithms of uniform transcendental weight, and simple rational prefactors. Our computation provides an independent check of a recent result for three-loop corrections to the soft anomalous dimension matrix that predicts the general infrared singularity structure of massless gauge theory scattering amplitudes. Taking the Regge limit of our result, we determine the three-loop gluon Regge trajectory. We also find agreement with very recent predictions for sub-leading logarithms.