Not only older than trees, but older than dirt.
Literally.
Dirt, in the sense of organic topsoil, requires plant life, and often the action of burrowing insects, reptiles, and mammals to form. The Appalachian range formed about the same time that life was first colonising land, ~480 mya, and it's likely that soil formation post-dates this by a significant extent.
This also means that the Appalachians have some of the oldest rivers in the world, including the ... inaccurately named ... New River, the Susquehanna, and French Broad River, all dating to ~260--340 mya.