Первое летописное упоминание о Себеже датировано 1414 годом. «В 1414 году великий князь литовский Витовт из Дриссы двинулся с войском против псковитян и, подойдя к Псковскому пригороду Себежу, взял его и сжег, а сам двинулся далее».
В 1535 году по приказу князя И.В. Шуйского на берегу озера было начато сооружение деревянной крепости. «1535. Того же лета июня 26 князь Великий Иван (Грозный) повелел воеводам своим князю Горбатому да Михаилу Кубенскому с силами, и поставили город за Опочкой на озере Себеж, Иван-город на Себеже».
Строительство крепости было поручено воеводе Бутурлину. Работы велись довольно быстро, и за каких-то два месяца укрепления были построены. С этого времени Себеж стал упоминаться как один из опорных пунктов на западных границах Русского государства.
Враги не раз пытались захватить крепость, но это им удавалось не всегда. Первое испытание — осаду польско-литовских войск — крепость выдержала в 1536 г. В феврале 1536 года польско-литовские войска под предводительством воеводы Немиры окружили Себеж. Около двадцати тысяч воинов пытались штурмом овладеть крепостью, но каждый раз отступали. Не выдержав ударов русских, воины воеводы Немиры были вынуждены отступать на озеро. Лед не выдержал, и многие из них утонули.
Быть может, к этому времени и относится рождение второй легенды об истории названия города: много раз пытались враги захватить крепость на озере, гласит она, но каждый раз противник отступал от ее стен к «себе ж». Но все-таки в 1562 году польские войска ворвались в крепость и сожгли ее.
С 1579 года крепость находилась под властью Польши, в течение 2-й половины XVI — начале XVIII веков неоднократно возвращалась России и снова захватывалась Польшей. В 1772 году, получив статус города, Себеж окончательно вошёл в состав России. С 1777 года Себеж уездный город Полоцкого наместничества, с 1796 года — в Белорусской губернии, с 1802 года — Витебской губернии.
Во время Отечественной войны 1812 года корпусом Витгенштейна на высотах, впереди Себежа, были устроены шанцы, состоящие из вала и рва, с намерением воспрепятствовать французскому войску проникнуть к Пскову и Петербургу. Себеж стал штаб-квартирой корпуса графа Витгенштейна и ожидал возможного нападения со стороны занятого французами Полоцка.
29 мая 1885 г. пожар истребил дотла главную часть города, в том числе небольшой деревянный домик «на Замке», где останавливались Петр I и Александр I. После пожара последовало восстановление: заново выстроена деревянная синагога, находившаяся к тому времени, видимо, в центральной части.
В начале XX века город делился на три главных района: собственно Себеж, «Батарею» и пригород Песчанку. На полуострове в 80-е гг. XIX века были проведены большие мероприятия но благоустройству и подсыпке узкой части — Переволоки. Эта часть становится центром и застраивается парадными зданиями. После подсыпки Переволока стала пригодна для застройки, и, таким образом, город получил необходимую цельность и законченный центр.
В 20-х гг. Себеж превратился в пограничный город и часто переходил из области в область: в 1924 он стал уездным центром Псковской губернии, в 1927 — районным центром Великолукского округа Ленинградской, а в 1929 — Западной области, с 1935 — Калининской области. С 1957 года — в Псковской области.В годы Великой Отечественной войны Себеж был оккупирован немецко-фашистскими войсками 9 июля 1941 года. Город не был сметен с лица земли только в силу своего природного местоположения, но промышленные пригороды, вокзал, районы жилой застройки на Батарее, деревянная застройка в центре были в основном уничтожены. Освобождён — 17 июля 1944 года войсками 2-го Прибалтийского фронта в ходе Режицко-Двинской операции.
