Superconductivity is abundant near quantum-critical points, where fluctuations suppress the formation of Fermi liquid quasiparticles and the Bardeen-Cooper-Schrieffer theory no longer applies. Two very distinct approaches have been developed to address this issue: quantum-critical Eliashberg theory and holographic superconductivity. The former includes a strongly retarded pairing interaction of ill-defined fermions, the latter is rooted in the duality of quantum field theory and gravity theory. We demonstrate that both are different perspectives of the same theory. We derive holographic superconductivity in form of a gravity theory with emergent space-time from a quantum many-body Hamiltonian - the Yukawa SYK model and finite-dimensional generalizations thereof - where the Eliashberg formalism is exact. Exploiting the power of holography, we then determine the dynamic pairing susceptibility of the model. Our holographic map comes with the potential to use quantum gravity corrections to go beyond the Eliashberg regime.