Prawdopodobnie pierwszą lokację miasta, jeszcze na prawie polskim, otrzymała Tuchola już w XIII w. Jednak znany potwierdzony na piśmie przywilej lokacyjny dla Tucholi wystawiono w Malborku, dnia 22 lipca 1346 r. Wielki mistrz Heinrich Dusemer von Arfberg nadał miastu przywilej prawa chełmińskiego. Ówczesna Tuchola składała się z dwóch zasadniczych części, tj. miejskiej i zamkowej. Zabudowa wewnątrz miasta była głównie drewniana, a do murowanych obiektów zaliczała się gotycka fara pw. św. Bartłomieja oraz ratusz. Murowany prawie w całości był również kompleks zamkowy. Tak miasto, jak i zamek otaczały mury obronne i system fos.
W 1330 r. Tuchola stała się siedzibą komtura, który władał komturstwem o znacznym terytorium. Oprócz szerokich okolic Tucholi w granicach komturii znalazły się: Brusy, Swornegacie, Leśno, Wiele, Piechowice k. Kościerzyny oraz Odry czy Łąg. Z czasów komturstwa swą nazwę wywodzi także miejscowość Wdzydze Tucholskie położona nad brzegiem jeziora Wdzydze.