We report the first use of a coincidence technique to study neutrinoless double--electron capture (0$\nu$ECEC) to an excited state in the daughter nucleus. We investigated 0$\nu$ECEC by $^{112}$Sn leading to the possibly degenerate 1871 keV excited state in $^{112}$Cd by searching for its de--excitation $\gamma$ rays of 1253 keV and 618 keV in coincidence. The experiment was performed at ground level. A sample of 3.91 g of tin enriched to 99.5\% in $^{112}$Sn was placed between two high--purity germanium $\gamma$--ray detectors. In order to enhance the sample material, rods of natural tin totaling 1.2 kg (natural abundance 0.97\% $^{112}$Sn) surrounded the cylindrical surface of our two $\gamma$--ray detectors. After an exposure of 1.59 kg $\times$ days of $^{112}$Sn, no decays were observed. From this null result we determine a lower limit for the half--life time of T$_{1/2}> $2.7(1.3) $\times$ 10$^{19}$ yr (68\%(90\%) CL). We hope to achieve a sensitivity in the 10$^{23}$ to 10$^{24}$ yr range with a sample of a few kg of $^{112}$Sn and improved $\gamma$--ray detectors in an underground facility.