Datowane na lata 1464–1480 Insignia seu clenodia Regis et Regni Poloniae polskiego historyka Jana Długosza, uznaje herb Ostoja za rdzennie polski. Zapisuje on informacje o herbie wśród 71 najstarszych polskich herbów szlacheckich we fragmencie: „Ostoya duas lunas defectuosas ceruleas, dorsis contra se tendentes, cruce eciam cerulea illas intersecante, in campo rubeo defert Genus Polonicum loquax et arrogans.”.
Ewolucja wizerunku
Pierwotnie w miejsce miecza znajdował się w herbie krzyż, zaś w klejnocie głowa smoka z długą szyją między dwoma księżycami. Elementy te ulegały na przestrzeni dziejów znacznym zmianom. Stałe były tylko – tynktura pola, oraz obecność księżyców.
Pole czerwone przypisali Ostoi autorzy średniowiecznych herbarzy Bellenville, Gelre, Lyncenich, Bergshammar, Stemmata polonica, Złotego Runa, oraz Jan Długosz w Klejnotach i kronika Soboru w Konstancji. Te same źródła podały księżyce w pas, barkami do siebie. We wszystkich księżyce są złote, oprócz Herbarza Złotego Runa, gdzie narysowano je srebrne.