Считается, что город вырос на месте погоста (своего рода постоялого двора), заложенного киевским князем Олегом Вещим в зиму 885–886 годов во время ежегодного сбора дани – Большого полюдья. Из-за удачного географического расположения здесь вскоре начали появляться первые переселенцы – ремесленники и земледельцы, обеспечивая быстрый рост населения и территории города.
В XIII веке во время Батыева нашествия город был уничтожен монголо-татарами.
С середины XIV века – центр княжества в Великом княжестве Литовском. Сильно пострадал в 1379 году от войск Дмитрия Донского.
В 1503 году переходит под юрисдикцию Великого княжества Московского.
Долгое время город находился на юго-западной окраине Русского государства и не раз подвергался нападениям польско-литовских сил, как, например, в 1515, 1534 и 1535 годах.
Летом 1535 года во время Стародубской войны польско-литовское войско под командованием гетманов Радзивилла и Тарновского, захватив, разорило город и сожгло крепостные стены, при этом погибли 13 тысяч жителей.
Но в том же году город со всеми укреплениями был заново отстроен. Укрепления состояли из валов, рвов и деревянных рубленых стен с проездными башнями.
В 1563 году впервые упоминается о существовании в Стародубе двух крепостей, большая из которых находилась на левом берегу речки Бабинца, а другая, меньшая («часть форштата») в Заречье. По сохранившимся планам того времени видно, что объёмно-планировочная структура города была почти такая же, как и сейчас, и напоминала радиально-кольцевую.
В 1616 году поляки вновь овладели городом, и по Деулинскому перемирию сохранили его за собой.
В 1620 году король Сигизмунд III даровал жителям вольности по Магдебургскому праву, а городу – герб, изображающий старый дуб с орлиным гнездом. В королевской грамоте говорилось о Стародубе, как о пограничном городе, «валами оточенном и… способном к обороне». Польша использовала его укрепления для защиты своих земель от Московского государства.
В 1646 году весь край был отнесён к Гетманщине. А в 1654 году, когда Гетьманщина соединилась с Россией, и Стародуб стал полковым городом – административным центром Стародубского полка в составе Гетманщины.
В 1660 году был разорён крымскими татарами, а в 1663 году – поляками.
На землях Стародубщины, начиная с 1660-х годов, основываются многочисленные старообрядческие слободы.
Со второй половины XVII века Стародуб становится одним из важнейших центров ярмарочной торговли между польскими, украинскими и русскими городами. На две крупные ярмарки – Соборную и Десятуху привозились разнообразные товары в большом количестве: пенька, масло, мед, воск, меха, поташ, стекло. Местное купечество было известно своим богатством.