Lots of small soil arthropods
I make the prediction that the soil evolved around 350 million years ago (mya) and base this on the animals found in the soil. By looking at when each of these creatures were first around, we should be able to get a better picture of when the soil evolved. 

I also predict that there were two waves of colonisilisation/creation of the soil of/ by small arthropods and worms. 
The first wave
was in symbiosis with growing plants. The springtails jumped out of the sea and earned a living keeping plants healthy.  Some springtails graze the roots, and others pass on vital spores to create mychorriza This collaboration called Mycorriza between roots and fungi is becoming sufficienly well know to turn it into a commodity. You can now buy bags of it. . When the going gets rough for springtails, they spring out of the way.
However the Mycorriza can only help the roots if their spores find their way to the roots. The springtails know as Onychiururids are  to collect fungal spores accidentally on their collophores. These sticky protuberance on their abdomen gives rise to the latin name of springtails - collembola.  This transfer of fungal spores is like the accidental transfer of pollen that is carried out by bees. So these springtails - onychiurids, are like the bees of the soil - accidentally transferring spores. While that is an accidental affect, why are they there in the first place.  Current thinking is that these sticky protuberances play a role in osmosis water intake and excretion - all functions important to springtails dealing with dry conditions. However it is also possible they are involved with the sexual process. where males lay spermatophores,  and females pick them up later

Streptomyces bacteria produce the substance geosmin - that gives that earthy smell after the rain. "Researchers discovered geosmin specifically attracts springtails, whose antennae can directly sense geosmin. The researchers suggest both organisms evolved together, the Streptomyces serving as food for the springtails, while the springtails subsequently spread bacterial spores helping seed new Streptomyces colonies. There is mutual benefit. The springtails eat the Streptomyces, so the geosmin is attracting them to a valuable food source. And, the springtails distribute the spores, both stuck on their bodies and in their faeces, which are full of viable spores, so the Streptomyces get dispersed. This is analogous to birds eating the fruits of plants. They get food but they also distribute the seeds, which benefits the plants.” The authors say this goes back 500mya. I believe it is about 350-400mya

"This symbiotic relationship is key to the survival of Streptomyces The bacteria produces certain antibiotic compounds that make it toxic to other organisms such as fruit flies or nematodes. Springtails, on the other hand, generate a number of novel enzymes that can detoxify the antibiotics produced by Streptomyces. Streptomyces spores cannot be distributed by wind and water in the soil, because there are only small air compartments in the soil, These small primitive animals have become important in completing the lifecycle of the Streptomyces, one of the most important sources of antibiotics known to science."

But what happened to that debris? This was the second wave and arthropods stepping up to make use of a waste product, otherwise being washed away. All those essential elements wasted. When autumn leaves began to fall, plant remains  were washed , along with volcanic dust, into the oceans. 

According to the Geological Society Volcanism, Impacts and Mass Extinctions:
‘the most prominant feature of the oceans were the black shalefacies. Several elements contributed to increased nutrient influx and eutrophication of the oceans, during Variscon Orogony and the evolution of plants and phosphorus from volcanic ashes’ 

The second wave 
The second wave of small soil arthropods, the mites, and dealt with the debris. They - somehow - came on to the land (from sea?) to with the debris, and in so doing made the soil complete. Because the valuable essential elements were being held where they were needed instead of being lost. They were being recycled . Perhaps the first great lesson in how to deal with was waste! When the environment gets rough for the mites, they roll up i a ball and wait for it to get better. Other mites prey on the springtails. They've been doing it for over 350 million years. 

See what you think? I have broken my analysis down into the following six small soil animals, the main groups of soil animals, and what they did co-evolving with plants getting 'Higher'.

i. Springtails ii. Mites iii. Nematodes iv. Earthworms v. No Insects vi. Insects

They provide great diversity of species - and have the same biomass as the massive earthworms. Yet they seem to get ignored. One learned paper put that down to the problem that there are a lot of them to count and there arent many people to do it. I once did. I counted half a million of them. 

To give you an idea of how many of these creatures exist in British soils, I could tell you how long I would have had to have lived, counting at that rate, to count the estimated number in Britain. I would have had to live twice as long as the earth to reach the target of 12 quadrillion. 12 thousand trillion creatures most with distringuishing features, are arthropods and worms, interacting to provide the most important 'service' to humanity, yet most of us havent a clue what they look like or do.

Soil would not exist, but for the soil mesofauna. Soil does not merely “harbour” soil animals. They are part of what makes soil – as opposed to clay/minerals/sediment/sludge, a living entity. The early arthropods (mites and springtails) co-evolved with the soil over a period of less than 50 million years. The mesofauna role is integral to the complex development that turns lumps of chemicals into a rich living substance. When you pick up a lump of soil, it is alive due to the actions of the fungi and bacteria with these myriads of small arthropods breaking down lignin and the like, to put back into the life cycle. Quite simply life as we know it would not exist without speck sized oil animals . 

The dominant compounds of are completely different from the originating minerals; witness the clay lattice, which is based on Aluminium, which is otherwise rare in rocks. One day soil can be hard, next soft, then runny or friable. Its texture changes in a way no other substance does. We should not treat the soil like dirt. To give an idea of its organic/biological complexity, Rothamsted Research Station are going to try to map the genome of the soil (check out). It is what turns this lump of rock called a planet into the Earth.

It is hard to imagine, when you are standing on that clod, that underneath each footprint, there are tens of thousands of living animals moving around. Yet it all looks still. It is a bit like when I am told that table top consists of trillions of electrons flying round in a vacuum at the speed of light. But do make leap. By looking at these small creatures, you find mainly mites and springtails, and small ‘round’ worms called nematodes. They vary in numbers according to Ph, crop etc. But what is noticeable is the lack of insects.

i. Springtails

Springtails are generally considered to be creatures a more primitive than insects While they have the classic 6 legs of insects, they also have the strange springing tail. 15-20% of soil mesofauna is made up of springtails Springtails are attested to since the Early Devonian.[9] The fossil from 400 million years ago, Rhyniella praecursor, is the oldest terrestrial arthropod, in Scotland.

Collembolans are omnivorous, free-living organisms that prefer moist conditions. They are good at avoiding desiccation - so they are the first out of the extraction systems. They do not directly engage in the decomposition of organic matter, but have a close relationship with the roots, and fungi. They may well set up mychorhiza fungi by bringing in their spores to grow in the roots, and then the fungi use sugar from the roots as energy, and in exchange pass nutrients from the soil to the roots. This increases the effective reach of the roots. The word "collembola" is from the Greek colle meaning glue and embolon meaning piston or peg.

In sheer numbers, they are reputed to be one of the most abundant of all macroscopic animals, with estimates of 100,000 individuals per cubic meter of topsoil, essentially everywhere on Earth where soil and related habitats (moss) cushions, fallen woodgrass tufts, ant and termite nests) occurThey tend to be the soil inhabitants living closest to the surface – otherwise their springtails – presumably some sort of defence mechanism, are not much use, if they buried underground. You find springtails gazing roots, presumably eating sloughed off material. They can look a bit like rabbits, especially group called Sminthurids.
Springtails are attested to since the Early Devonian.[12] The fossil from 400 million years agoRhyniella praecursor, is the oldest terrestrial arthropod, and was found in the famous Rhynie chert of Scotland. Given its morphology resembles extant species quite closely, the radiation of the Hexapoda can be situated in the Silurian420 million years ago [13](from Wiki) . 

ii. Mites

¾ of all soil mesofauna are oribatid mites. These really big numbers of oribatid mites make, what EO Wilson the well known entomologist and socio-biologist says, are the most important creatures. He said we should know about them – rather than your fancy creatures, yet only 2 people in the US could identify any of them[1]. These, along with nematodes and earthworms, are responsible for the greatest numbers in soil – throughout the world. They are simply most important creatures on – and certainly – in, earth. These colonise most soils, and clearly are key in breaking down leaves, making the plant debris ready, increasing the surface area, for the fungi to breakdown further to the constituent metabolites.
Soil living Oribatid mites look like a cross between miniature turtles and spiders. There are getting on for 10,000 described species, with the total number may be 100,000. Fossil oribatid mites are known from Devonian sediments indicating an age of at least 380 million years. Their densities reach from a few hundreds per square meter in intensively used agricultural sites up to 500,000 in acidic soils of northern boreal forests. The oribatid mites eat the plant debris, breaking down the materials and producing nutrients (such as?), which plants can then absorb through their roots.
"We conclude that this oribatid group, central to the trophic structure of the soil food web, diversified in the early Paleozoic and resulted in functionally complex food webs by the late Devonian." 
 There is another large group of mites found in the soil -predatory mesostigmatic mites.. About half of the 10,000 known species in the suborder Mesostigmata are predatory and cryptozoan - permanently living under conditions with high relative humidity. Many of them can be found wet soil; living in the soil-litter, rotting wood, dung, carrion, nests or house dust). Look at that long proboscis, ideal for piercing skin and sucking out the contents of a nematode.
Talking of which..

iii. Nematodes

Nematodes are the most abundant type of animal on earth, and live in hot springs, polar ice, soil, fresh and salt water, and as parasites of plants, vertebrates, insects, and other nematodes. They have no segments and are really just a piece of gut. Members of the phylum Nematoda (round worms) have been in existence for an estimated one billion years, They are thought to have evolved from simple animals some 400 million years before the "Cambrian explosion" of invertebrates and another 100 million years before the birth of the soil. However their simple structure has meant there are v few fossils until 100-150 mya – when they got caught in amber. This is because they are soft bodies and slough off their outer cuticle. It makes them one of the most ancient and diverse types of animals on earth. So they would have been in at the beginning of soil formation. .It is difficult to use the evolution of nematodes to help pinpoint the birth of the soil, but clearly they fit in with the predicted evolution of the soil. They would have been there before, but invade easily and provide ‘the meat’ for others.

Nematodes contend with voracious predators, changes in soil temperature and moisture, and the death of its host plant. The study of nematode predators and pathogens is important because nematode predators can be used (in theory) to control populations of plant-parasitic nematodes. The most common method plant nematodes use to evade predation is by living inside plant tissue or by limiting their mobility in the soil environment. By spending less time moving in the soil, a nematode can reduce its chance of "running into" a predator or pathogen. Some plant nematodes spend most of their time in the soil (ectoparasites) and others are mostly contained within the plant tissue (endoparasites).

Nematode survival is against abiotic ones such as temperature and water availability. The onset of winter or the drying of the soil can be disastrous for a nematode. Many are capable of cryptobiosis (hidden life): the ability to enter a state of suspended metabolic activity during unfauvorable environmental conditions (drying, heat, cold). These can often survive for years in a cryptobiotic state awaiting favourable conditions that will trigger their revival. The ability to undergo cryptobiosis makes it very difficult to eradicate from a field.

iv. Earthworms

There is more written on earthworms, starting with Darwin, than all the other soil animals put together. (Darwin and earthworms). After all a lot easier to see. Darwin got his children to test how they reacted to various substances and developed the theory that they were useful to the soil - not pests.. I am not sure he saw their evolutionary role - Darwin's more famous theory, with the soil. They have the same biomass and carbon capturing capacity as all the soil mesofauna. although we hear a lot more about thee earthworms. (Soil Fauna and Carbon Cycling).

There are three main sorts of earthworms when categorised by feeding behaviour “Epigeic” worms are surface active, pigmented non-burrowing worms with relatively high reproductive rates which consume decaying plant residues on the soil surface. “Anecic” worms build vertical burrows in the soil which descend into the mineral horizons but they feed at the surface usually at night. “Endogeic” worms inhabit the organo-mineral and deep horizons, constructing branching sub- and horizontal burrows and they feed on more humified organic matter. More on Biodiversity.

Meysman, Middelburg, and Heip. 2006. Bioturbation: a fresh look at Darwin's last ideaTRENDS in Ecology and Evolution, Full version, click this space!. It says: "From an evolutionary perspective, recent investigations provide evidence that bioturbationhad a key role in the evolution of metazoan life at the end of the Precambrian Era. Key to 27 UK species of UK earthworms

v. No Insects

As important as is what is in the soil, it is also instructive to notice what isn't there. There are virtually no insects that live all their lives in soil. There are quite a lot who live one stage of their lives ( usually larval - eg several fly larvae) but not all of their lives. Remember insects are classified according to their wings, which means they are all some sort of flyers.

Only the first four Goups/Orders represent soil mesofauna in most soils globally. This indicates that soil evolution of the composite body took place before many of shifts in tectonic plates that make up our world today. As once in soil, there is not a lot of travel going to be possible. This explains why the existing species of OTUs do not cross all soil types. In fact most cover only a few. Only 14 out of nearly 3000 species are found in 4 or more locations (Molecular Study)

The big worms are the massive diggers and movers. Each segment of their bodies have muscles in order to push through the soil and churn up the stuff in side.But the breakdown of plant debris takes place outside the worms. The many thousand mites are the ones who do the chewing. Strongly protected they can clearly withstand massive changes in conditions – from bone dry to active soil almost immediately on adding water. And they are working away while it is freezing cold just above. They are most numerous in autumn, breaking down the plant debris, as everything else is dying off. They have been around a long time.

vi. Insects
What is most noticeable is the lack of insects that spend their whole life underground. There are a few larvae in the soil, but in terms of the rest of the soil mesofauna, relatively few live their lives their. Ants get closest and eat the oribatid mites, so are part of the soil food chain.
The first insect is 400 million years old. The oldest definitive insect fossil is the Devonian Rhyniognatha hirsti, estimated at 396-407 million years old.[5] This species already possessed dicondylic mandibles, a feature associated with winged insects, suggesting that wings may already have evolved at this time Like other insects of its time, Rhyniognatha presumably fed on plant sporophylls - which occur at the tips of branches and bear sporangia, the spore-producing organs. The plants were not as differentiated – consisting of two forms – vegetative and spore, whereas later we had the whole explosion with sexual reproduction. All after soil was evolved, but due to the soil to recycle all those metabolites – and can produce a rich vegetation to feed many millions more insects. But they needed the soil for stability and to grow bigger than ever before evolution of wings -- winged insects first appeared in the fossil record around 350 mya. Insects evolved from then – into the air. They are described and categorised by their wings – most of the orders (check) end in ptera , which equals ‘wing. So you have the Coleoptera – hardwinged insects better known as beetles. Diptera (flies) 2 (instead of 4) winged, Lepidoptera (Scaled wings). Mayflies and Locusts appeared 300 mya, Beetles & Flies – 275mya , Wasps/bees 225 Butterflies 200 mil, and mantids, cockroaches, and parasitic wasps all appeared during the Jurassic explosion of insect numbers up to about 150 mya.
They colonised the air and the trees and plants that arose from this new stable recycling substrate called soil. By now the soil was as metabolic body whose parts consisted of a living web of roots, fungi, and all sorts of spores, plant debris, small but many scavengers, predators, herbivores, and fungivores are well established and working together. The evolution of two very different taxa – mites and trees, at the same time speaks volumes. .

So the presumption has to be that the soil evolved before insects. And when insects evolved – mainly to colonise the air, they did not have much success in the soil, as it was already completely colonised. There was no ecological niche available in which they could fit. Virtually no insects spend their whole lives in the soil – ants and termites come closest. Ants are known to eat oribatid mites (E O Wilson), so become part of the food soil web. Other insects spend only part of their lives in the soil - sometimes as pupa (moths) and sometimes as larvae the likes of leatherjackets (daddy longlegs) and wireworms (click beetle). Are they always considered as ‘pests’?

[1] E.O Wilson and oribatid mites http://barelyimaginedbeings.blogspot.com/2009/08/oribatids-rule.html

[2] http://www.mansfield.ohio-state.edu/~sabedon/biol3060.htm