Hot carrier dynamics critically impacts the performance of electronic, optoelectronic, photovoltaic, and plasmonic devices. Hot carriers lose energy over nanometer lengths and picosecond timescales and thus are challenging to study experimentally, whereas calculations of hot carrier dynamics are cumbersome and dominated by empirical approaches. In this work, we present ab initio calculations of hot electrons in gallium arsenide (GaAs) using density functional theory and many-body perturbation theory. Our computed electron-phonon relaxation times at the onset of the Γ, L, and X valleys are in excellent agreement with ultrafast optical experiments and show that the ultrafast (tens of femtoseconds) hot electron decay times observed experimentally arise from electron-phonon scattering. This result is an important advance to resolve a controversy on hot electron cooling in GaAs. We further find that, contrary to common notions, all optical and acoustic modes contribute substantially to electron-phonon scattering, with a dominant contribution from transverse acoustic modes. This work provides definitive microscopic insight into hot electrons in GaAs and enables accurate ab initio computation of hot carriers in advanced materials.