Стародубский полк был самым обширным из всех десяти полков Малороссии. В состав его входили округи двух древних центров северской земли — Стародуба и Новгорода-Северского, каждый из которых в период феодальной раздробленности был центром самостоятельного княжества. После образования государств Русского и Литовского, расположенная на их пограничье Северская земля обратила на себя притязание обоих государств. Войны между Москвой и Литвой велись преимущественно за обладание Северской землёй.
В 1618 году, по Деулинскому перемирию, утверждённому затем в 1634 г. Поляновским договором, Северская земля была уступлена Литве.
В составе Речи Посполитой, Стародубщина относилась к Смоленскому воеводству, хотя территориально не была связана с его основной частью.В 1654 году Стародубщина вошла в состав Нежинского полка как автономная территория, которую возглавлял наказной полковник. Придя к власти в 1663 г., Иван Брюховецкий провел административную реформу, направленную на послабление огромного Нежинского полка, где преобладали сторонники его политического оппонента, нежинского полковника Василия Золотаренко. Среди прочего, им была выделена отдельная административная единица из Нежинского полка — Стародубский полк.
В 1668 г. Пётр Дорошенко, который занял Левобережье и вытеснил Брюховецкого на юг, создал из сотен Нежинского и Стародубского полков Новгород-Северский полк, куда вошли Новгород-Северская и Шептаковская сотни. Но новый левобережный гетман Демьян Многогрешный в начале 1669 г. упразднил Новгород-Северский полк и восстановил прежнее административное деление.
