XIII sajandil asus praeguse kiriku ja lossivaremete kohal tõenäoliselt eestlaste linnus. Kivilinnuse rajamist alustas ordumeister Goswin Herike 1357. aastal. Nähtavasti leidis ehitamine aset mitmes etapis. Karksi linnus kujunes Viljandi kõrval teiseks väga võimsaks linnuseks.