Résumé : We introduce and solve a model of interacting electrons and phonons that is a natural generalization of the Sachdev-Ye-Kitaev-model and that becomes superconducting at low temperatures. In the normal state two Non-Fermi liquid fixed points with distinct universal exponents emerge. At weak coupling superconductivity prevents the onset of low-temperature quantum criticality, reminiscent of the behavior in several heavy-electron and iron-based materials. At strong coupling, pairing of highly incoherent fermions sets in deep in the Non-Fermi liquid regime, a behavior qualitatively similar to that in underdoped cuprate superconductors. The pairing of incoherent time-reversal partners is protected by a mechanism similar to Anderson's theorem for disordered superconductors. The superconducting ground state is characterized by coherent quasiparticle excitations and higher-order bound states thereof, revealing that it is no longer an ideal gas of Cooper pairs, but a strongly coupled pair fluid. The normal-state incoherency primarily acts to suppress the weight of the superconducting coherence peak and reduce the condensation energy. Based on this we expect strong superconducting fluctuations, in particular at strong coupling.