花崗岩質のバソリスの上に町はあり、先史時代とローマ以前の遺跡が残る。

ローマ時代、町はトゥルガリウム（Turgalium）と呼ばれた。後にイベリア半島へ西ゴート族が来襲しても、町の人口は属州ヒスパニア時代から定住するローマ系市民が優勢であった。イスラム支配下では、バダホスに本拠を置くイスラムのタイファに属した。500年に渡る異教徒の支配のもと、幾度ものキリスト教国軍の侵攻が続き、1186年にアルフォンソ8世によって征服された。しかしムワッヒド朝が勢力を強めてくると再度征服し、再びキリスト教徒の町となったのは1232年、フェルナンド3世の時代であった。1430年、フアン2世が都市の地位を授けた。当時既に、市城壁の外にはユダヤ人の定住地があった。人口が増加するトルヒーリョは、次第に城壁の外へ、囲い地の外へ拡大していった。

現在のマヨール広場は、新大陸へ探険にいったトルヒーリョ出身者が帰国後建てた、壮麗な邸宅で飾り立てられた。

フランス軍が侵攻した時、住民だけでなく建物や公文書も損傷を受けた。