Narodil se 2. srpna 1948 v Hythe, hrabství Kent, Anglie. Dětství prožil v srdci kentských lesů a v rozlehlých pustinách u Romney Marsh.
V letech 1967–1970 navštěvoval vysokou školu v severním Walesu, kterou absolvoval s titulem z aplikované zoologie. Na londýnské škole hygieny a tropické medicíny vystudoval obor lékařská zoologie v roce 1971. V následujících třech letech pracoval v lékařském výzkumu v Konciliu lékařských objevů. Roku 1975 přešel na dráhu profesionálního spisovatele.
V roce 1968 mu vyšla povídka v New Worlds a pak několik roků pokračoval přispíváním do časopisů. V 70. a 80. letech publikoval tři SF romány, pod různými pseudonymy publikoval řadu hororů a thrillerů, z nichž nejznámější je cyklus Nighthunter (pod jménem Robert Faulcon). Psal dokonce i románové přepisy TV seriálu Profesionálové (pod jménem Ken Blake).
Jeho rané povídky vyšly ve sbírce In the Valley of the Statues (1982). Tato sbírka obsahovala také jeho úspěšnou novelu Mythago Wood (Les mytág, čes. 1994) z roku 1981. V roce 1984 ji rozvedl do románu, jenž se stal přelomovým dílem jeho kariéry. Román byl oceněn World Fantasy Award a British SF Association Award. Na Les mytág volně navazují romány Lavondyss (1989, čes. 1995) a The Hollowing (Hloubení, 1993, čes. 1995). Dějovým předchůdcem prvního románu je novela The Bone Forest (Les kostí, 1991, čes. 1996), která vyšla ve stejnojmenné sbírce a před lety i v Ikarii.
I poté, co se věnoval dalším románům, neopustil již Holdstock mytologicko-fantazijní látku. Mýty a parapsychické schopnosti kombinuje román The Fetch (Fantom, 1991, čes. 1996), krajina lidského nevědomí a starodávná města ožívají v románu Ancient Echoes (Dávné ozvěny, 1995, čes. 1997), artušovská legenda v titulní novele sbírky Merlin´s Wood (Merlinův les, 1994, čes. 1999), následoval román Gate of Ivory, Gate of Horn (Brána ze slonoviny, brána z rohu..., čes. 1998) a artušovský motiv s keltskou mytologií znovu ožívá v dvoudílném Merlinově kodexu, Celtika (Keltika, 2001, čes. 2001) a The Iron Grail (Železný grál, 2002, čes. 2002), autor pracuje na dalším dílu Broken Kings (měl by vyjít v listopadu 2006). Všechny české knihy vyšly v nakladatelství Polaris.
Mezi jeho koníčky patří mytologie, folkloristika (sbírá rituální masky) a vážná hudba. Roku 2002 navštívil Eurocon konaný v České republice.
Robert Holdstock nyní žije v severním Londýně, ale utíká do lesů a pustin, kdykoli je to možné.