Borgen Søborg lå oprindelig på en holm i den nordlige halvdel af den nu udtørrede Søborg Sø. Søborg nævnes med al sandsynlighed første gang i Saxos beretning om, hvordan kong Valdemar den Store i 1161 indtog ærkebisp Eskils unavngivne borg og by, der lå på en holm i Ledre Sø. Eskil havde sandsynligvis opført borgen i årene ca. 1137‑55. Det ældste borganlæg bestod af et stort ottekantet tårn, der siden blev nedrevet i forbindelse med opførelsen af en større borg med palatium, der var den repræsentative hovedbygning, i tegl på 30,5 × 10,5 m, en rundkirke samt en ringmur forsynet med to tårne.
I 1200-tallet blev borgen udbygget med fløje op mod indersiden af en ny ringmur mod nord og vest. Selve borgholmen var omgivet af en ringgrav og en ydre vold mod nord, syd og øst. Adgangen foregik via en 75 m lang træbro, der førte ind til et stort porttårn forsynet med en vindebro. Forborgen lå på den mellemste holm.