Город возник в начале XX века на месте пересечения двух железных дорог, идущих в широтном и меридиональном направлении (Москва - Рига и Санкт-Петербург - Витебск). В 1925 году Новосокольники обрели статус города.

Название городу дала хищная птица сокол. В средние века люди, ловившие соколов и обучавшие их умению охотится на диких животных, назывались "сокольники". Так же стали именовать сборщиков дани для московского князя, так как она часто взималась в виде охотничьих соколов. Существуют и иные версии возникновения названия города.

Когда были построены две железные дороги, станция, расположенная на их перекрестке, недалеко от селения Сокольники, стала называться Новосокольники. Сокольники с тех пор именуют Старосокольники.

Город Новосокольники стал одним из крупнейших в области транспортных узлов и развивался достаточно быстро до середины XX века. Во второй половине века численность его населения почти не изменялась, оставаясь на уровне 10-11 тысяч человек.

Крепость на месте современного города была возведена в 1535 году воеводой царя Ивана IV (Грозного), в честь которого получила имя "Иван-город". Позже город стали называть по имени озера, на берегу которого он был расположен. Происхождение названия до конца не исследовано, но вероятно, что слово "себеж" означает землю, которая принадлежит отдельному владельцу ("себежнику").

В 1772 году Себеж, возвращенный России Речью Посполитой, получил статус города. Герб Себежа, как и Невеля, подобен символу города Полоцка. Но если герб Невеля имеет зеленый цветовой фон, то герб Себежа - голубой.

Себеж расположен в богатой озерами юго-западной части области, недалеко от границ с Республикой Беларусь и Латвией. Но город сильно удален от двух хозяйственных основных центров области и в XX веке развивался достаточно медленно. После выделения в отдельную административную единицу пгт Сосновый Бор население Себежа сократилось до 6 тысяч человек.