If the Sahara used to be fertile and has since experienced minimal rainfall causing the current desert conditions, where did all the sand come from? I assume the original dirt is still there, just underneath the sand.
The sand IS the original dirt, or at least what's left of it.
Sand is one of the major constituents of soil. Soils are roughly half minerals by volume and those minerals are silt, sand, and clay. In fact sand is often the largest single constituent of most common soils. Silt and clay are smaller and lighter, and can be moved by wind much easier when dry, this leads to the removal of everything but the heavier sand particles in very dry conditions. What has happened is that without water and life to bind the material together, wind has removed all the lighter particles leaving nothing but sand and pebbles. Wind is good at sorting grains by size so each area tends to only have one grains size.
Where it came from originally
. Sand is just weathered rock, if you look at a map of the sahara there are quite a few scattered mountains and highlands in the desert. That is where the sand (and the original silt and clay) came from originally, weathering of rock, and the sahara is mostly exposed rock, with sand only making up a minority of its surface.
I suggest the wiki for getting started on soil science, if you are interested, https://en.wikipedia.org/wiki/Soil
More on what sand is, http://www.sandatlas.org/sand/
More on wind driven sorting, https://people.ucsc.edu/~jzachos/migrated/eart120/lectures_08/LECT7B.pdf
Minimum volumes of mobile sand can be estimated for each region of the Sahara, such as the 26 meter average thickness of the Erg Oriental of Algeria. Sand migration model conclusions regarding such volumes of sand are that the current Saharan dune distribution and morphology took at least 1.35 million years to evolve, possibly much longer if there were long periods of aeolian quiescence. Independent geological evidence indicates that cycles of wet and dry periods have occurred over the past 20 million years, corresponding respectively to semi-arid periods of erosion (in the source areas), and to periods of hyper-arid redistribution of sand.
In less arid times vegetation grows on the dunes and stabilizes them.
Paleoclimate proxy data and computer simulations reveal that the Nebraska Sandhills likely had active sand dunes as recently as the Medieval Warm Period, when temperatures in the North Atlantic region were about 1°C (1.8°F) warmer than the current climate. Wikipedia
A thin layer of topsoil is formed.
Aerial photographs of the Spirit Dunes, Manitoba, Canada show this can happen in decades:
The Sahara dunes were still there during fertile times - they were just grown over with grass. When conditions became arid, what little topsoil there was blew away and/or was mixed with the sand.
Only 25% of the Sahara is sand and dunes. 70% of the Sahara is bare rock and stones.
Silicon makes up 27 percent of rocks on average. The Sahara is covered 25 percent by SiO2.
Algeria and Morocco are 800m average, Chad and Egypt are about 500m, Lybia and Mauritania are about 270m
The sand and rock material was there all the time, it's just been changed and collected into dune zones. The quartz is stronger and lighter and it sorts itself to the top, and the dark mafic minerals are sorted by gravity.
The Sahara has had aridity troubles for the last 30 million years, the alps are only 35 million years old. They say it was all green, perhaps like India, Nevada and California and Texas.
It's probably changed from desert to savanna many times in the last millions of years due to ice ages. Perhaps there was a kind of biannual monsoon during ice ages, and the monsoon transitions to the current rain habit every time for the past 35 million years, which is when the alps started forming.
The north african shield has zones hundreds of millions of years old, I cant find pages on the geology of N Africa, it is volcanically active: https://www.volcanodiscovery.com/north-africa.html The massive Atakor volcanic field is the largest in the Hoggar (or Ahaggar) volcanic province of southern Algeria and covers an area of 2150 sq km