When was the first not-icy desert formed?
Deserts have existed since at least the Permian period (299-251 million years ago) when the world's continents had combined into the Pangaea supercontinent. Stretching from pole to pole, this land mass was large enough that portions of its interior received little or no precipitation, according the University of California Museum of Paleontology.

Pangaea broke into smaller land masses which were moved across the surface by tectonic forces, a process that both changed global climate patterns and the climate those continents were exposed to. As a result, current desert regimes date back to no more than 65.5 million years, according to this Encyclopedia Britannica article:


  The desert environments of the present are, in geologic terms,
  relatively recent in origin. They represent the most extreme result of
  the progressive cooling and consequent aridification of global
  climates during the Cenozoic Era (65.5 million years ago to the
  present), which also led to the development of savannas and scrublands
  in the less arid regions near the tropical and temperate margins of
  the developing deserts. It has been suggested that many typical modern
  desert plant families, particularly those with an Asian centre of
  diversity such as the chenopod and tamarisk families, first appeared
  in the Miocene (23 to 5.3 million years ago), evolving in the salty,
  drying environment of the disappearing Tethys Sea along what is now
  the Mediterranean–Central Asian axis.


Which would put the oldest of "modern" desert somewhere in the region of what later became North Africa or South Asia.