Chemical structures are a tradeoff of several factors, including the conditions on how they were formed.
The stability of any given chemical structure depends on the ease with which any specific reaction can turn it into something else. Both graphite and diamond are very stable structures which basically means they are hard to easily convert into something else. Another way to think about this is that to convert either into a different allotrope (different versions of the same element) of carbon requires a lot of bonds to be broken and rearranged and this requires a big input of energy. That's why both are stable.
But why is there more than one stable allotrope of carbon? Note that there are more allotropes than just graphite and diamond: buckminsterfullere is also a stable allotrope of carbon with a completely different structure that involves molecules of 60 carbons not a covalent network solid. The basic answer is that there are a lot of ways to arrange the atoms to give a stable structure (partially because there are a lot of options for stable C-C bonds given the chemistry of carbon). This is related to the same reason that organic chemistry is a big subject: C-C bonds are very "stable" and can be organised to give a huge variety of structures.
Not every arrangement of C-C bonds is equally stable: many will fall apart into other structures because there are mechanisms that make the rearrangement easy. But there are no easy mechanisms for rearranging the bonds in diamond or graphite into something more stable. Buckminsterfullerene is only formed from a plasma of carbon atoms when it is allowed to cool: you can't just make it by simple routes from other allotropes of carbon.
Both graphite and diamond have very similar energies of formation at normal conditions, though graphite is marginally more stable (the particular arrangement of bonds has a slightly lower energy than the arrangement in diamond under normal conditions). But this is not true at all conditions. Under extreme pressures, diamond is more stable. And this is how diamond is formed: it crystallised from solution in hot melted volcanic rocks deep in the earth containing lots of carbon and under high pressure. In these conditions, diamond is the more stable way to arrange carbon atoms and the conditions are such that the less stable form will covert to the more stable form because there is enough energy around to break the C-C bonds until the most stable structure is created.
Normally (by which I mean at atmospheric pressure) carbon rich compounds can be pyrolised to give pure carbon in the form of graphite. Here the heat drives off the non-carbon atoms and the carbon atoms rearrange to the form stable at lower pressures.
Once formed neither major allotrope is easy to convert to the other without extreme conditions. Which is why you can wear diamond jewellery without constant anxiety.
In short the stable allotropes of carbon are a function of the way they were made. And there are a variety of ways to join carbon atoms up to give different structures. Once formed they don't easily interconvert. Hence we find a variety of allotropes depending on the variety of conditions that led to their formation.
NB carbon isn't the only element with multiple allotropes. Tin, for example, changes crystal structure and properties depending on the temperature (and, unlike carbon, this interconversion is fast enough to have been a problem in the era when tin cans were actually made of tin and stored in very cold conditions).