Tereny, na którym położone jest miasto, zasiedlone były jednak wcześniej. Prowadzone w latach pięćdziesiątych XX wieku prace archeologiczne dostarczyły licznych materiałów dowodzących istnienia grodu już w VII wieku. Nad Notecią na północny wschód od rynku odkryto ślady osady, portu oraz wału. W VIII-IX wieku użytkowana była osada nadrzeczna, a przystań w X-XII wieku. Kilkadziesiąt metrów na zachód od rynku archeolodzy odkryli ślady zachodniego fragmentu wału grodu, a na posesji przy południowo-zachodnim narożniku rynku, który znajdował się wewnątrz dawnego grodu, odkryto pozostałości drewnianych chat, ulic moszczonych drewnem, liczne fragmenty ceramiki i innych przedmiotów, a także szczątki zwierząt i ryb. Gród w Ujściu został rozbudowany przez Bolesława Chrobrego, stając się ważną twierdzą graniczną, strzegącą przeprawy od strony Pomorza. Gród ulokowany był w miejscu połączenia się dwóch rzek: Gwdy i NoteciLech Leciejewicz Ujście we wczesnym średniowieczu, Wrocław 1961. Słownik geograficzny Królestwa Polskiego odnotował również znaleziska archeologiczne jakich dokonano w XIX wieku.