Inspired by the recent experimental demonstration of ultrafast x-ray absorption spectroscopy, we present a framework for the calculation of extended x-ray absorption fine structure (EXAFS) spectra on the ultrafast (femtosecond to picosecond) time scale. Model calculations for gas phase I-2, evolving under the influence of laser pumping, demonstrate that ultrafast EXAFS has the potential to serve as a direct probe of nuclear dynamics, including time-dependent interatomic separations and relative orientations. The feasibility of ultrafast EXAFS as a viable and useful experimental technique is discussed.