Первые археологические находки на себежской земле датируют 7-10 веком новой эры и относят к древнерусской культуре.  Люди здесь жили давно, но основательное поселение появилось не сразу.  Изначально эти места обживали финно-угры, потом их сменили балты, затем пришли славянские племена.

Первое летописное упоминание о Себеже датировано 1414 годом.  Оно найдено в книге «Хроника Польская, Литовска, Жемойтская и всей Руси» летописца Мацея Стрыйковского.  По некоторым данным, в «хронике» содержится очень много отсебятины и фантастики, достоверность этого упоминания невысока.

В 1535 году на берегу озера было начато сооружение земляной крепости Ивангород-на-Себеже, для закрепления на занятых приграничных литовских землях.  С этого времени Себеж стал упоминаться как один из опорных пунктов на западных границах Русского государства.  В летописях это отражено так:

1535 г.  Того же лета июня 26 князь Великий Иван (Грозный) повелел воеводам своим князю Горбатому да Михаилу Кубенскому с силами, и поставили город за Опочкой на озере Себеж, Иван-город на Себеже.

Во время Северной войны Пётр I, прибыв в Себеж, лично руководил строительством укреплений, готовясь к сражению с армией шведского короля Карла XII.  «Петровская гора» — один из укреплённых пунктов — и теперь напоминает о тех, давно минувших временах.

В 1616 году Себеж был захвачен поляками.  1 декабря 1618 года, в соответствии с мирным договором, отошёл Речи Посполитой.  Согласно проведённой после этого инвентаризации, в городе насчитывалось 9 улиц, 6 церквей и 1 монастырь.

23 марта 1623 года король Сигизмунд III даровал Себежу Магдебурское право, регулировавшее общественно-политическую жизнь и сословное состояние горожан, и герб с самсоном, разрывающим пасть льву.  В 1625 году он же заложил деревянный костёл.

В декабре 1632 года, в ходе Смоленской войны, войска Русского царства вернули Себеж.  4 июня 1634 года был заключён мир, по которому Себеж снова отошёл Речи Посполитой.  В тот же год он был передан княжескому роду Родзивиллов в вечное владение.

В мае 1885 года центральная часть города до тла сгорела в пожаре.  Огнём было уничтожено около 600 построек.

В описании 1889 года указывается, что в городе имелось 8 кожевенных заводов, 2 гончарных завода, 3 синельно-набойных фабрики и паровая мукомольня; несколько позже появились кирпичный и пивоваренный заводы.

В 1908 году в Себеже появилось электрическое освещение улиц, в 1911 году открылся кинотеатр Жаржавского.