Про заснування цього поселення перекази свідчать таке. Під час набігів татар на Поділля воєвода Свищ разом зі своєю дружиною, рятуючись від переслідування, втік на Острів Буга і тут оселився. Так заснували містечко, яке мешканці обкопали захисними ровами. У середні віки все населення Острова вимерло від чуми. Страшний мор пройшовся цими місцями. Ті, хто залишились, спалили свої пожитки і покинули цю місцину. Тоді острів здобув назву Чорного.
1425 р. Чорний острів належав Іванові (Янові) Свірчу, наданий йому попередньо Вітольдом і в цьому ж році внаслідок обміну перейшов до Миколая Бедриха.
У XIV столітті це місце фігурує у джерелах під назвою Чорного городка, однак у другій половині цього ж століття — це вже Чорний Острів.
1493 Чорний Городок мав 18 димів.
1495 належав Новодворським.
Чорний Острів з 1545 р. належав Анні з Новодворських Влодковій — дружині старости Мацея Влодека. Пізніше він перейшов до її сестри Констанції Свірч. За часів Констанції король надав Чорному Острову Магдебурзьке право.
1552 року польський шляхтич Ян Каменецький — ротмістр корогви кавалерії оборони поточної — отримав у доживоття Чорний Острів (Подільське воєводство).
1592 р. племінник князя Дмитра Байди Вишневецького — Костянтин Вишневецький через одруження з Анною, отримав у володіння Чорний Острів, яким Вишневецькі володіли до 1744 р. Після смерті князя Михайла Серватія Вишневецького, місто перейшло його внучці — Катерині з Огінських Пшездецькій.
1671 р. Чорний Острів належав дядькові короля Михайла Вишневецького — князю Костянтину Вишневецькому, місто мало природний захист озерами та річкою Бог. На той час Чорний Острів був досить великим містом. 1667 р. татари не змогли взяти місто і відступили. В місті був дерев’яний костел та церква. Під ту пору усе місто було забудоване дерев’яними будинками. Замок знаходився на окремому острові і був оточений земляним валом та палісадом. Будинків в межах замку не було.
