Первые археологические находки на себежской земле датируют 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 году открылся кинотеатр Жаржавского.