A cornerstone of paired-electron superconductivity in Fermi liquids is Eliashberg theory. Eliashberg theory, that naturally accounts for a strongly retarded pairing interaction, has also been used to describe superconductivity near quantum critical points. A rather different perspective emerged with the notion of holographic superconductivity, rooted in the duality of quantum field theory and gravity theory. We will demonstrate that quantum-critical Eliashberg theory and holographic superconductivity are, in fact, different perspectives of the same phenomenon. We will derive holographic superconductivity in form of a gravity theory with emergent space time from a quantum many-body Hamiltonian where the Eliashberg formalism is exact. To this end we focus on the quantum-critical transition to superconductivity in a generalisation of the Sachdev-Ye-Kitaev (SYK) model.