Using ultrafast x-ray probing, we experimentally observed a progressive loss of ordering within solid-density aluminum as the temperature raises from 300 K to >10{4} K. The Al sample was isochorically heated by a short ( approximately ps), laser-accelerated proton beam and probed by a short broadband x-ray source around the Al K edge. The loss of short-range ordering is detected through the progressive smoothing of the time-resolved x-ray absorption near-edge spectroscopy (XANES) structure. The results are compared with two different theoretical models of warm dense matter and allow us to put an upper bound on the onset of ion lattice disorder within the heated solid-density medium of approximately 10 ps.