Tårnet stammer fra begyndelsen af 1200-tallet, hvor det blev bygget ovenpå nogle af ruinerne fra Kejser Trajan's store Markedskompleks, der dækkede området oppe fra Monte Magnanapoli mellem nutidens gader Salito del Grillo og Via IV Novembre og den udgravede bakkeskråning ned mod Trajan's Forum i dalen nedenfor højen.

For enden af Markedskompleksets store hal lå der et område, der var brolagt med travertinfliser og forsynet med vandbassiner. Man mener, at der måske har været fiskemarked i denne del, som senere blev base for middelaldertårnet Torre delle Milizie, som stadig rager op over komplekset. Det er dog også muligt, som Sergio Delli foreslår, at der tidligere har ligget i vagttårn her i forbindelse med den gamle Servius-Bymur, hvoraf man stadig kan se rester på den nærliggende Largo Magnanapoli og mellem markedsruinerne ud mod Salita del Grillo.

Er dette tilfældet, forstår man bedre den gamle antagelse om, at det var her, at Nero stod og betragtede den store brand, der i år 64 efter Kristus lagde store dele af det nedenforliggende område øde. (Tårnet kaldes også populært Torre di Nerone)

Området kaldtes i begyndelsen af Middelalderen for Contrata Militiarum fordi Kejser Tiberius II Constantinus' hær, Militiae Tiberianae, på det tidspunkt (578-582) dominerede området, da longobarderne mere og mere havde taget herredømmet på den italiske halvø og også var nået frem til at hærge i landskabet omkring Rom, så der opstod hungersnød i byen og man fra Byzans måtte beordre skibe afsendt fra Ægypten med kornforsyninger. Den byzantinske milits blev indkvarteret i Markedskomplekset og heraf opstod stednavnet "de Militiis", der blev brugt som tilnavn til forskellige kirker i kvarteret, for eksempel skal der ved Via Biberatica have ligget en kirke viet til Sant'Abbaciro og ud mod Salita del Grillo kirken San Salvatore de Militiis.

I 1200-tallet var området i familien Arcioni's eje. Familien havde flere huse på et areal, der tilsyneladende strakte sig over Quirinalhøjens skråning, hvor nu Via IV Novembre møder Via della Pilotta og op til Via XXIV Maggio, hvor Kirken San Silvestro bar tilnavnet de' Caballo de' Arcioni, og herfra ned til Monte Magnanapoli og området med de mange ruiner fra det gamle Markedsanlæg.

Det var sandsynligvis i det 13.århundrede, at rester af mure fra den øvre del af Trajan's anlæg blev ombygget til et fæstningstårn, som også fik tilnavnet "de Militiis". Måske blev det bygget af en vis Pandolfo della Suburra eller af Pave Gregor IX (1227-1241). (Andre bud på en bygherre er: Alessi- eller D'Alessio-familien, hvor Pietro Alessio's sønner skulle have ladet tårnet opføre omkring år 1200. Denne familie var iøvrigt den ovenfor nævnte Pandolfo's velyndere). På dette tidspunkt var også de andre ruiner blevet inkorporeret i de befæstede anlæg, som datidens mægtige - og krigeriske - familier lod opføre, når de stredes om magten i byen. .

Senere overgik ejendommen til Annibaldi-familien, som fik titlen "Dominus Militiarum" eller "de Militiis", men som i 1301 solgte den til Pave Bonifacius VIII af Caetani-familien, som sammen med Ærkepæsten ved Lateran-Kirken Gherardo Bianco bekostede en restaurering af Tårnet, hvorefter det blev overdraget til Pavens nevø Pietro Caetani, der på dette tidspunkt overtog titlen "Dominus Miliciareum Urbis" fra den detroniserede Annibaldi-familie. Tårnet benævntes i denne periode "Castello dei Caetani" eller "Loggia dei Caetani". Ifølge Flavio Biondi var det Bonifacius, som lod Tårnet opføre på resterne af en gammel kirke, der måske var viet til San Silvestro eller San Martino. (Paven citeres for at have ladet opføre ialt 3 tårne (Torre delle Milizie, Torre del Grillo og et ikke navngivet) på ruinerne af 3 kirker viet til San Basilio, San Silvestro og San Martino).

Nogle mener, at arkitekten for byggeriet var Marchionne d'Arezzo, der også stod for opførelsen af Torre dei Conti og Torre del Grillo.

Ud mod Via Biberatica kan man se rester af murværk i tuf, mens det øvrige byggeri er udført i teglsten. Tufmuren er opført i Middelalderen, da man udbyggede de tidligere mure til fæstning.

I 1310 erobrede Roms befolkning i samarbejde med Colonna-familien det befæstede tårn, hvorfra man uden held bekæmpede Henrik VII af Luxembourg, hvis hærfører Ludovico di Savoia til gengæld havde held til at erobre bygningen. Henrik VII, der var kommet til Rom i 1311 for at blive kronet, overdrog tårnet til Caetani-familien i 1312, men allerede i 1319 havde denne problemer med ejerskabet og bad nu Hertug Charles d'Anjou af Calabrien om hjælp.

I 1330 overtog Annibaldi-familien atter Tårnet, men Henrik VII gennemtrumfede atter - efter et sammenstød med Riccardo Orsini og Annibaldo degli Annibaldi - at Caetani-familien blev ejere. For Caetani-familien var Tårnet af stor strategisk betydning, fordi de herfra kunne overvåge det store befæstede område, som den fjendtlige Colonna-familie havde opbygget på den anden side af Monte Magnanapoli, samt det befæstede område, som Conti-familien havde opbygget omkring Via di Tor de' Conti.

I 1348 ødelagdes den øverste del af Torre delle Milizie af et stort jordskælv, som måske også har skadet det øvrige kompleks og i hvert fald også ødelagde det nærliggende Torre dei Conti. Dette ejedes af den magtfulde Conti-familie, som på et tidspunkt udvidede deres besiddelser på højen. Torre delle Milizie tilhørte i hvert fald denne familie omkring midten af 1500-tallet, hvor den almindelige opfattelse af de resterende ruiner var, at de stammede fra et antikt badeanlæg.

I 1573/1574 solgte familien nogle huse ved Monte Magnanapoli samt det jordstykke, hvorpå den forfaldne Tårnruin stod, til Suor Maria Vittoria Massimo, der havde til hensigt her at opføre et Kloster for Dominikaner-nonner.

I 1628-1641 udvidedes Klosteret og der opførtes en større Kirke viet til Santa Caterina da Siena. Nonnerne var glade for deres have og spadserede ofte tur heri, ligesom de tit gik op i Tårnet, hvorfra der naturligvis var en pragtfuld udsigt over Rom.