La història d'Olocau del Rei comença amb la construcció d'un castell àrab, cridat Olcaf, sobre l'actual Puig d'Olocau, a 1200 m d'altura, si bé és segura la presència de doblament iber en eixe mateix punt. En 1184 Alfons II d'Aragó va concedir el castell, després de la seua conquista, als cavallers de l'Orde de Sant Joan de Jerusalem. Això Explica que en un principi el castell i la vila d'Olocau van formar part del Regne d'Aragó, ja que el seu castell va ser conquistat per Alfons II en 1180, cinquanta anys abans de començar la conquista del Regne de València, i Donat el mateix any a l'Orde de l'Hospital.
Un altre fet important en la història d'Olocau del Rei és l'atorgament de la Carta de Poblament per l'infant El senyor Pedro en 1271, document que encara podem observar en l'Arxiu Municipal. Per esta Carta de Poblament, Olocau s'agrega al Regne de València, fet decisiu en la seua història. La data d'adhesió al Regne de València seria qüestionable, ja que el Cid ho va annexar després d'una batalla. El dia 14 d'agost de 1084, el Cid Campeador, recolzat pel que seria el seu consogre, el Comte de Barcelona D. Ramón Berenguer III (1082-96), amb l'ajuda del Rei El senyor Sancho Ramírez I de Navarra (1063.94) va alliberar una gran batalla contra el rei de Lleida, Tortosa i Dénia el musulmà Mundir-al-Hadvid (1081-1090). Després de derrotar els àrabs es va firmar la pau, i per a poder conservar esta posició, el Cid va fortificar el castell d'Olocau i així poder dominar l'extensa zona de Morella.
El 30 de setembre de 1287 s'agrega per privilegi al terme general de Morella. De Morella es va segregar adquirint entitat pròpia com a municipi el 1691, per privilegi de Carles II. Posteriorment va participar en les Guerres de Successió i Carlistes.