The first written information confirming existence of Kostelec dates from 22nd August 1362.
It mentions an introducing of a priest Heřman to the presbytery of Kostelec.
Its patron was the lord Mikuláš Piskle of Červená hora.
But we can assume, that the village already existed before this date – maybe since the end of the13th century. In that time, colonizing effort of members of the family with a golden stirrup in their heraldry, culminated. Sezema founded the castle of Červená Hora and Tas the castle of Vízmburk.
The colonization was mainly realized by native, Czech people.
If there was a church in Kostelec, then it is certain, that there must have existed a presbytery covering its neighbouring villages. Moreover, the name “Kostelec” came from the Latin word “castellum”, so there must have been a yeoman’s fort that was not an independent domain.
In the 16th century, this yeoman’s grange was in possession of the family of lord Sendražský from Sendraž.
References to a church of Kostelec from 1370 and 1408 confirmed an existence of the presbytery that belonged to the deanship of Dobruška, again. In the Hussite period, an owner of the Kostelec domain was Hynek from Dubé, junior, avowed objector of allowing bigger religious freedom. But most people stood on Hussites` side. The presbytery of Kostelec passed over to Calixtines` possession as well. At the end of the 16th century the first Lutheran priests came to Kostelec, the last one was forced to leave the town in 1625.
In the half of the 15th century is by Silesians destroyed Kostelec mentioned together with Úpice among small towns belonging to the domain of Vízmburk. Just at this time, (1447) a small town belonged to the domain of Náchod from 1497 till the abolition of subjection. In the 16th century, the least heiress of the Sendražský family left the forest, meadows and field to the presbytery. The fort was taken down and out of its stone, there was built a new church, to replace the old, only wooden one. In 1591, the church has burnt down together with part of the small town. The fire destroyed municipal documents as well as documents of the presbytery. There was only one thing, which was saved – tinny font from 1555, which is the oldest physical relic of the town until now.
Before the small town managed to recover from such a disaster, the Thirty Years` War began, and raging of imperial and Swedish soldieries, bad harvest and hunger with it. After the war only 42 houses were inhabited, the number of citizens didn’t reach two hundreds and only one quarter of fields was cultivated. Surprisingly, in spite of the next one hundred relatively peaceful years, a number of citizens didn’t grow overly. In 1780, there were 68 houses in Kostelec. A number of peasants decreased, whereas the number of crofters rose almost seven times.
Kostelec was called a townlet that time. This is confirmed by its seal from 1680 on which there is the oldest picture of the symbol of the town.