Na obszarze miejskim wykopano monety rzymskie z czasów Trajana, 2 fibule oraz artefakty celtyckie.
Pierwsza wzmianka o Ujściu w dokumentach pisanych pochodzi z 1108 roku z kroniki Galla Anonima i odnosi się do wojen prowadzonych przez Bolesława Krzywoustego w celu przywrócenia Pomorza Polsce. Najcięższe walki z Pomorzanami to okres panowania Bolesława Krzywoustego, zwłaszcza rok 1108, kiedy Bolesław udał się na Węgry. Okazję wykorzystał książę pomorski Gniewomir, który z powodzeniem oblegał gród, zdobywając go. Gniewomir przyjął chrzest i zarządzał grodem. Mimo powrotu Bolesława Krzywoustego z wyprawy, nie udało mu się jednak odbić grodu.
Kolejna wzmianka o Ujściu pochodzi z żywotu św. Ottona zapisanego w Prüfening w 1125. Biskup bamberski Otto wracając po odbyciu wyprawy chrystianizacyjnej na Pomorzu, przebyć miał straszną puszczę i dotrzeć do grodu Ujście położonego na najdalszych kresach Polski.