Interatomic Coulombic Decay (ICD) is a relaxation phenomenon, which takes place in weakly bound atomic and molecular systems, typically within a few to hundreds of femtoseconds depending on the system and the particular decay mechanism. The creation of ICD-active states requires the production of highly excited systems, usually populated by innershell ionization or excitation. To this end, XUV and X-ray radiation from synchrotrons was conventionally applied for the majority of experiments due to the desired state-selective ionization of certain sub-shells. The advent of Free-Electron Lasers (FELs) has enabled an entirely new class of experiments, which finally allow to trace ICD directly in the time domain due to the femtosecond pulse duration. Within this paper, the first time-resolved ICD measurement using an XUV-pump-XUV-probe scheme will be discussed in detail. The experiment was performed on neon dimers and ICD was triggered by removing a 2s electron from one of the neon atoms using a 58 eV pulse from the FEL in Hamburg (FLASH). The onset of ICD was probed with a delayed copy of the trigger pulse that further ionized one of the two Ne+ ions emerging after ICD. Thus, the delay-dependent yield of coincident Ne+ + Ne2+ ion pairs contains the lifetime of the 2s-innershell vacancy decaying via ICD. The result of 150 fs ± 50 fs is in good agreement with theory but only for those calculations that explicitly take nuclear motion into account.