I think Hardy's Tess Of The D'urbervilles uses Stonehenge as a location towards the end of the book (been an age since I read it).
Harry Harrison wrote a fantasy book called 'Stonehenge' set during the supposed building of it.
Does anyone know the earliest example in fiction ?
Off the top of my head I can only think of Sir Walter Scott, Kenilworth (c1810) where he features the then Wayland's Cave and the Blowing Stone?
VBB