Theory predicts that double-core-hole (DCH) spectroscopy can provide a new powerful means of differentiating between similar chemical systems with a sensitivity not hitherto possible. Although DCH ionization on a single site in molecules was recently measured with double-and single-photon absorption, double-core holes with single vacancies on two different sites, allowing unambiguous chemical analysis, have remained elusive. Here we report that direct observation of double-core holes with single vacancies on two different sites produced via sequential two-photon absorption, using short, intense X-ray pulses from the Linac Coherent Light Source free-electron laser and compare it with theoretical modeling. The observation of DCH states, which exhibit a unique signature, and agreement with theory proves the feasibility of the method. Our findings exploit the ultrashort pulse duration of the free-electron laser to eject two core electrons on a time scale comparable to that of Auger decay and demonstrate possible future X-ray control of physical inner-shell processes.