A mitjans del segle XI Ramon, fill de Ledgardà va jurar a Ramon Berenguer I fidelitat pels castells de Tudela i de Fornells. També en aquesta època, el germà de Ramon, que era abat i es deia Berenguer, va jurar fidelitat al comte per aquest castell. Dins del mateix segle XI trobem documentats diferents senyors d'aquest castell com Ramon Mir de Tudela, Arnau Giuillem de Tudela i el fill d'aquest anomenat Guillem.

L'any 1136 el comte Ramon Berenguer IV i el senescal Guillem Ramon, de la família dels Montcada, van signar un pacte per diversos castells entre els que es trobava el de Tudela. En 1291 l'infant Pere es va casar amb Guillema de Montcada, que va rebre com a dot aquest castell. A partir d'aleshores va passar a mans de la família Montcada, tot i que en van cedir la jurisdicció als Cartellà, tal i com consta en documents de l'any 1314, quan Ermessenda de Cartellà era senyora dels castells de Rocacorba, Tudela i Colltort.

En el cim de la muntanya de Sant Grau trobem restes d'un antic poblat ibèric, descobert en 935, però no excavat mai, el castell de Tudela i l'església de Sant Grau.

El castell està gairebé enrunat totalment. De l'edifici del segle XII només s'ha conservat la base d'una torre circular.

El fragment conservant no supera els dos metres i mig d'alçada, ja que en època moderna es van aprofitar part dels murs del castell per construir-hi una masia Això també va influir en el fet que no s'hagin conservat fragments més importants del castell.

La capella de Sant Grau apareix documentada des de 1548, tot i que es creu que es va edificar sobre l'antiga capella del castell. Està formada per una sola nau capçada a l'est per un absis semicircular i dues capelles laterals. La façana es va reformar a principis del segle XIX i estava coronada per un campanar de cadireta, avui desaparegut. 

En l'actualitat, en l'espai del castell i de la capella s'ha ubicat un punt de vigilància forestal i un mirador, que permet gaudir d'unes meravelloses vistes.