Niezwykle cennym świadectwem z dziejów rodu Ostoja jest plomba drohiczyńska z połowy XIII w., na której widnieje znak rozpoznawczo-własnościowy z godłem herbu Ostoja. Reprezentował on Strachotę, syna Mikołaja ze Ściborzyc, a został zapewne wyciśnięty stemplem w latach 1253–1255. Plombę znaleziono w ruinach fundamentów dawnego zamku w Drohiczynie. Zamek ten należał do księcia mazowieckiego Siemowita I, który po 1252 r. wizytował w Drohiczynie dwukrotnie. Zapewne Strachota Mikołajewic ze Ściborzyc, przyboczny i najbardziej zaufany rycerz księcia, towarzyszył mu podczas tamtych wizyt na drochiczyńskim zamku.

Jedną z najstarszych pamiątek rodu Ostoja jest pieczęć dziekana poznańskiego Czcibora (Ścibora) odciśnięta w wosku przedstawiająca herb Ostoja. Godło herbu jest dziś nieczytelne, ale zachował się jego opis z 1879 r. – [...] (pieczęć) przedstawia na tarczy trójkątnej godło rodu Ostojów; napis: S’Cztiborii Decani Pozn. Ścibor był dziekanem katedry poznańskiej w latach 1356–1363. Dokument z jego pieczęcią znajduje się w Archiwum Archidiecezjalnym w Poznaniu (syg. DK, perg. 81).