Enligt sägnen grundlades Lenaborg av Birger Jarl. Utgrävningar har bekräftat att stenhusset byggdes på hans tid. De visade också att det kan ha funnits en äldre, enklare träborg på höjden. Den borgen kan ha varit samlingsplats för hären som kom att möta de danska trupperna i slaget vid Lena.

Det stenhus som byggdes vid mitten av 1200-talet tycks ha varit ett försvarbart slott snarare än palatsartad borg. Läget, med vid utsikt över landskapet valdes till en del förmodligen för att vara väl lämpat för försvar. Det var ett relativt högt stenhusbygge. Det var inte ovanligt att adel och stormän lät bygga försvarsanläggningar på sina gårdar. Till vardags bodde de inne i en timrad mangårdsbyggnad nere på gården.

Exakt hur det sett ut som byggnad vet man inte. Man antar att borgen bestått av ett 33 x 13 meter stort rektangulärt stenhus i 3 våningar. Väggarna var av natursten, och av kalkbruk och Östertorps sand. I bottenvåningen bör det ha varit kök och förrådsutrymmen. Bostad för borgsherren och riddarna fanns på de övre våningarna, medan det fanns plats även för tjänstefolk och vaktstyrka.

En av de mäktigaste stormännen i landet vid 1200-talets slut var Torgils Knutsson, som tog sin tillflykt in i Lena år 1305. Det är troligt att han då lät befästa borgen. Kung Birger Magnussons bröder gjorde uppror och tillfångatog både kungen och Torgils, till de dog av Nyköpingshus 1318. Egendomen på Lena, med kungsgård, gårdar och borg lämnades då över till Linköpings stift. ”Palatset” kan möjligen ha rasat till sin ruin redan efter det att länsmän från Linköpings stift.

Kanske började man redan då ta sten från ruinen för att bygga andra byggnader på gården. Ruinen fridlystes av landshövdingen 1875, men hindrade inte att den användes som stenbrott ännu en tid. Idag ser man rätt tydligt formen på det rektangulära palatset högt ovanför åkern. Man skymtar delvis murarna i den källarvåning som hört till huset. En grundlig grävning gjordes här 1987–88, varpå området städades. Då fann man flera spår av väggar, eldstad, en stentrappa samt källarvalv vid huvudbyggnaden.