Древнейшие поселения в этой местности относятся к V в. до н. э. Эстонское городище была основана не позднее эпохи викингов. Первое письменное упоминание относится к 1154 году, когда арабский географ Аль-Идриси впервые нанёс его на карту мира. [1] В XII веке вокруг городища появляется первое постоянное поселение. В начале XIII векa эти земли были завоёваны Орденом меченосцев. В 1224 году вместо деревянных укреплений началось возведение мощной крепости Ордена, которая временами считалась мощнейшей на Балтике. На протяжении последующих 200 лет она всё время достраивалась и модернизировалась.

В 1283 году рижский архиепископ даровал окружающему крепость Феллин поселению статус города[2].

В начале XIV века Феллин становится членом Ганзы и важным пунктом в торговле Ганзы с Россией, что привело к процветанию города. В 1365 году Феллин участвовал в подписании мира между Ганзой и Данией. Во время Ливонской войны город и крепость Феллин был частично разрушен. Ещё большие разрушения произошли во время русско-польской войны начала XVII века, после которой от прежней мощи и великолепия города остались только несколько стен. В XVII веке, находясь под шведским господством, Феллин был лишён статуса города. В 1783 году Екатерина II вернула этот статус и сделала Феллин центром уезда. С ростом экономического и политического влияния возрастало и население Феллина.