The notion of spontaneous formation of an inhomogeneous superconducting state is at the heart of most theories attempting to understand the superconducting state in the presence of strong disorder. Using scanning tunneling spectroscopy and high resolution scanning transmission electron microscopy, we experimentally demonstrate that under the competing effects of strong homogeneous disorder and superconducting correlations, the superconducting state of a conventional superconductor, NbN, spontaneously segregates into domains. Tracking these domains as a function of temperature we observe that the superconducting domains persist across the bulk superconducting transition, T c, and disappear close to the pseudogap temperature, T, where signatures of superconducting correlations disappear from the tunneling spectrum and the superfluid response of the system.