Vēsturnieki pēc dažādiem netiešiem dokumentiem un arheoloģiskiem atradumiem velk paralēles starp mūsdienu Starokostjantiņivas pilsētu un senās Bolohivas kņazistes Kobudu. Mūsdienu apdzīvotā vieta pirmoreiz minēta 1505. gadā kā Koliščencu(Колищенці) ciems Polijas karaļa rīkojumā par ciema nodošanu kāda Ivana Labunska īpašumā. 1561. gadā Labunska pēcteči pārdeva ciemu kņazam Konstantīnam Ostrožskim. Trīs mēnešu laikā Ostrožskis panāca no Polijas karaļa privilēģiju dibināt ciema vietā pilsētu un tai Magdeburgas tiesības. Ostrožskis izveidoja pilsētu par savu dzimtas rezidenci un pārdēvēja to savā vārdā par Kostjantiņivu(Констянтинів), bet pēc vēl vienas pilsētas — Novokostjantiņivas — dibināšanas, pirmo 1632. gadā pārdēvēja tagadējā vārdā. 16. gadsimta otrajā pusē pilsētā tika uzbūvēts cietoksnis (1571), 5 baznīcas, kā arī preču noliktavas gadatirgu vajadzībām. 1620. gadā pilsēta pāriet kņazu Zaslavsku īpašumā, bet 1682. gadā — kņaziem Ļubomirskiem. 1793. gadā pilsēta nonāk Krievijas Impērijas sastāvā un 1796. gadā tai apstiprinātas Volīnijas guberņas apriņķa pilsētas statuss.[1]