Первым достоверным и подкрепленным документально упоминанием о Себеже, как о постоянном опорном пункте, служащим базой, складом и арсеналом для походов в Литовское княжество, является строительство первой деревянной крепости, или острога, в 1535 году. Возведено это фортификационное сооружение было в стратегически удобном месте, практически со всех сторон окруженном водой, воеводой Бутурлиным, по приказу московского князя. Холм, находящийся на оконечной части вытянутого с запада на восток полуострова, и возвышающийся над ним, представлял собой идеальное место для постройки оборонительного пункта, предполагая также сам способ его возведения. Видимо, в том числе и поэтому, Себежская крепость была одних самых важных по значению форпостов на новых территориях московского княжества, занятых в период русско-литовской войны 1534-37 г.г.
Архитектором первой крепости был итальянец, Петрок Малый (он же Пётр Франческо (Францизско) Анибале), который был архитектором высокого уровня. Возведена первая крепость под его руководством была меньше, чем за месяц. Стены этой крепости представляли собой высокий земляной вал с частоколом из заостренных бревен. Следует отметить, что свою оборонительную функцию эта крепость выполнила весьма успешно, так как по утверждению более поздних источников, относящихся к XVII веку, ее не могло взять двадцатитысячное литовское войско.
В крепости была также построена церковь Усекновения главы Иоанна Крестителя, отчего первое название города было Ивангород-на-Себеже, но оно не прижилось, и город стал далее именоваться более кратко – Себежем.
В XVI веке Себеж играл довольно большую роль, прикрывая с юга Опоченскую крепость, которая ранее одна сдерживала атаки литовского войска. Именно там 27 февраля в 1536 году случилось так называемое "Ледовое побоище под Себежем".
Судьба города-крепости Себежа была непростой. Предполагается, что в первый раз крепость была захвачена войском Стефана Батория примерно в 1580-81 годах.
В 1618 году, по условиям перемирия, положившего конец длившейся с 1609 года русско-польской войне, Себеж отошел к Речи Посполитой и был пожалован во владение роду Радзивиллов. Именно в этот период оконечная возвышенность полуострова стала называться Замковой горой.
В состав Российского государства Себеж снова вошел в 1654 году, во время русско-польской войны 1654-1667 годов.
В 1678 году, в результате нового перемирия, закрепляющего Киев за Россией, Себеж, Невель и Велиж с уездами вошли в состав Речи Посполитой, снова став собственностью семейства Радзивиллов.
Себеж также косвенно был затронут и Северной войной, между Швецией и коалицией государств Северного союза, в котором Польша и Россия воевали на одной стороне. В 1705-07 годах Себеж дважды занимали войска Петра Первого, как союзника курфюрста Саксонского и короля Польского Августа Второго. Во время этой войны город сильно пострадал, сократившись с 300 домов в конце XVII века до 140. Кроме того, он был почти полностью уничтожен пожаром 1762 года. Окончательно в состав Российской империи Себеж вошел только в конце XVIII века, в результате раздела Речи Посполитой в 1772 году.
Себеж не раз страдал от пожаров и переходил из рук в руки, поэтому история строительства и восстановления Себежской крепости во времена правления Алексея Михайловича, происходившая в 1656 году, может опираться только на немногочисленные документы той эпохи и предположения, основанные на них.
По данным Писцовой книги Себежского уезда "в верхнем городе анбар, а под ним погреб, в нем стоит зелье, и свинец, и ядра и всякий пушечный запас". Также упоминается про три полные государевы житницы в самом городе и девять пустых.
Так что, скорее всего, если проанализировать эти сведения, в 1585-1587 гг, к которым относятся данные Писцовой книги, крепости, как таковой, уже вероятно не существовало, и население ее значительно уменьшилось.
Перед московским государем вновь встала задача об укрепление важного приграничного опорного населенного пункта.
В этот раз строители новой крепости, в отличие от воеводы Бутурлина времен Ивана Третьего, особым энтузиазмом не отличались. К тому же, строительство новой крепости, взамен сгоревшей и разрушенной, предполагалось силами местного населения. Жители Себежа также, по-видимому, не горели желанием тратить силы на заготовку леса и строительство острога, ссылаясь на свою бедность и разорение.
Свидетельством этому предположению служит челобитная себежского воеводы Степана Бухвастова. В тексте этого документа говорится о том, что 21 января 1656 года воеводой получена грамота от царя Алексея Михайловича с указом заготовить в зимнее время лес, чтобы по весне восстановить земляную острожную крепость, "устроить острог хоти небольшой со всеми крепостьми и на Себеже твоего Государева окольнева города от летних ворот и до тех же летних ворот 704 сажни. Да в том же окольнем городе крем город и той кремской стены в длину от окольной стены 78 саженей а поперег той кремской стены десять семь сажень а кремского валу от воды в высоту до стены десять шесть сажень а окольнего города высота валу от воды до городовой стены десять сажень а поперег окольнева города от стены до стены сто тридцать сажень а в длину в окольнем городе от летних ворот до крему 190 саженей".
В этой же челобитной воевода ссылается на трудности заготовки и транспортировки леса, которого на восстановление "твое государево старое городище 21 тысяча деревьев" и то, что "на пустом городище на Себеже никаких мастеров нет кому твой государев острог делать", то есть что нет ни мастеров острожного дела и нет людей, которые бы заготавливали лес.
Пишет воевода царю также, что мастера острожного дела есть только в Опочке, крепости, в которой как раз в тот период находился большой стрелецкий гарнизон. Сетует воевода и на то, что просил он для выполнения царского указа у опочинского воеводы, князя Хилкова Ивана Андреевича, откомандировать 50-60 человек стрельцов, а у дьяка Меркулы Крылова прислать из Пскова, или псковских пригородов, русского попа, но до 9 февраля ответа от них так и не получил. И что на "пустом городище", без попа люди умирают, не приняв покаяние, а без казаков и стрельцов восстановить крепость совершенно невозможно. И для подкрепления своих слов прилагает челобитную от посадских людей и волостных крестьян.
В этой челобитной староста посадских людей, Иван Девкин и староста волостных крестьян, Грибанов Иван, жалуются на то, что силами населения себежского уезда поставленную царем задачу по устроению острога выполнить никак невозможно, что помимо хлебных подвод, взятых царским окольничьим, Дмитрием Алексеевичем Долгоруким, на содержании находятся еще и казаки, и шляхта, которые "правят и на наш хлеб деньги и харчи и всякий домовой запас". Поэтому просят в своей челобитной жители города и крестьяне возложить расходы по возведению острожной крепости не только на Себежский уезд, а на пригороды Пскова, находящиеся поблизости – Резитский, Лютинский и Красногородский.
Далее, после приложенной челобитной от крестьян, воевода пишет, что 24 февраля с поручением от Полоцкого воеводы, Дмитрия Алексеевича Долгорукого прибыл его порученец, стрелецкий сотник Яков Харламов, с требованием предоставить подводы с лошадьми для перевозки хлебных запасов из Пскова в Полоцк. Жалуется воевода и на беспредел, творимый шляхтой и казаками, что те забирают подводы у местных крестьян и отправляют вместо своих. Пишет, что крестьяне себежские бедны и до конца разорены, а князь Иван Андреевич Хильков и дьяк Меркула Крылов так и не прислали стрельцов и попа.
Следующий документ, по которому можно отследить движение дела по восстановлению старой земляной крепости – это челобитная – доклад царю Алексею Михайловичу от его, как предполагается, судя по тексту, эмиссара, присланного в Себеж с инспекцией, Василия Неплюева.
Докладывает Неплюев о том, что по состоянию примерно на конец марта заготовлено 6 тысяч 650 бревен (вместо необходимой 21 тысячи). Повторная царская грамота о восстановлении острога была получена 27 марта (упомянута в докладе). Неплюев, на основании поручения и грамот организовал совещание с посадскими людьми о том, можно ли устроить оборонительную стену меньшей протяженности, т.е. "малый острог", видимо потому, что предыдущие доклады воеводы Бухвастова о состоянии дел счел малоубедительными, особенно в той части, где он ссылается на неумение посадских людей в отношении "острожных работ". Они же оказались вполне компетентны в этом вопросе и в ответ на запрос Неплюева "посадские лучшие люди и староста Ивашка Девкин с товарищи мне холопу твоему о том говорили что малово острогу на которыми дел нельзя утвердить". Поэтому, на утверждение царю предлагается решение начать восстановление крепости с летних ворот, "потому что у летних ворот ныне без крепости нельзя быть". Судя по всему, по сохранившемуся началу ответной на донесение Неплюева царской грамоты и другим документам, царь утвердил предложенный им план.
Далее отчет о дальнейших работах следует в челобитной Василия Неплюева, ответной на царскую грамоту, присланную 20 июля 1956 года. Отчитывается он о том, что от восстановленных летних ворот по обе стороны поставлены "да две башни угольных башня Пятишная а другая Святская" и что ограда из кольев по "всему летнему пути" восстановлена и имеет протяженность четыреста шестьдесят саженей. Далее он также, как и ранее Бухвастов, упоминает о том, что в возведении предыдущей крепости принимали участие другие уезды и что силами одного Себежа полностью крепость восстановить нельзя, что при этом существует опасность нападения неприятеля с незащищенного "зимнего пути", по замерзшей воде.
Похоже, что в качестве превентивной меры, судя по докладной челобитной Неплюева, царь обязал усилить охрану на литовской границе, о чем и направил грамоту псковскому воеводе Ивану Андреевичу Хилькову, где по царскому указу "велено им во всем Псковском пригороде к воеводам и к приказным отписать чтоб во всех литовских пригородах жили с великим бережением по город и по воротам и отъезжие сторожи в которых местах давелось держати и проезжие станицы".
Дальнейшее развитие событий по восстановлению Себежского острога можно предположить из челобитной Тимофея Щербатова и Лариона Пашина, которая была составлена спустя два года после первого указа по восстановлению Себежского острога. В ней они докладывают о том, что в распоряжении царя, содержавшегося в грамоте, присланной в Псков 28 июня 1658 года, требуется произвести ревизию состояния Себежа, а именно: осмотреть "старой тайник большово города", под которым, скорее всего, подразумевается либо тайный колодец в крепости, либо тайный ход к источнику воды, а также оценить и записать объем сделанных по восстановлению в крепости работ. Без воды и восстановленных оборонных сооружений крепость не могла быть готова к "приходу воинских людей", то есть возможному появлению неприятеля. Для этих целей в Себеж был откомандирован Ипат Вараскин. Все материалы по результатам его обследования скрепленные печатью Пскова, были отправлены царю в Москву 28 ноября того же года. Курьером же был отправлен Якушка, псковский пушкарь.
Из сохранившихся источников можно предположить, что за исключением "летнего пути", возведенного Василием Неплюевым, обороноспособность крепости за прошедшие два года так и не была восстановлена окончательно.