Su historia está vinculada a la encomienda de la orden de Calatrava que tenía su sede en Alcañiz. En 1179 el rey Alfonso II de Aragón los territorios en los que se asienta Torrevelilla a la orden de Calatrava. En 1414 seguía perteneciendo a la misma orden.

 

Se cree que el origen del municipio se forma a partir de una propiedad de la familia Velilla alrededor de la cual surge una pequeña aldea. Surgiendo así la Torre de Velilla.

 

Pronto pasó a depender de la Orden de Calatrava, manteniéndose bajo el control de la encomienda hasta la disolución del régimen señorial. En el siglo XVII consiguió de Felipe III de Aragón un privilegio para tener horno y molino independiente de Castelserás.

 

En 1750 se segrega Castelserás de Alcañiz, junto con esa población, Torrevelilla se segrega y queda dependiente de Castelserás. En 1770, recibió el título de «villa», que fue efectivo a partir del 2 de Febrero de 1771, segregándose de Castelserás y manteniendo su independencia como municipio, aunque hasta 1812, no dispondrá de plena jurisdicción propia. En esa fecha el concejo de Torrevelilla se incorpora al régimen general de la nación.

 

En su pasado Torrevelilla mantuvo litigios con La Codoñera por el territorio situado en la margen derecha del río Mezquín. El litigio tuvo su final en 1855.

 

En cuanto a administración, Torrevelilla ha formado parte, de forma sucesiva, a la Encomienda de Alcañiz de la Orden de Calatrava y al corregimiento de Alcañiz (1711-1833). Se constituye como Ayuntamiento en 1834 y forma parte del partido judicial de Alcañiz.