Die Stöffelburg wurde vermutlich im 12. Jahrhundert von den Edelfreien von Stöffeln als Höhenburg erbaut. Im Jahr 1300 übergaben Kuno, Albrecht und Konrad von Stöffeln ihre Burg und die Stadt Gönningen nach einem Konflikt an Graf Eberhard den Erlauchten von Württemberg. Nach seinem Tod kam die Stöffelburg in den Besitz von Graf Ulrich III. von Württemberg und dessen Schwager Rudolf von Hohenberg. Beide verglichen sich am 10.11.1329 wegen Burg Stöffeln und der Stadt Gönningen, 1339 ging die Burg ganz in württembergischen Besitz über. 1345 wurden die Güter an Ulrich Truchsess von Urach verpfändet, der auf der Burg seinen Wohnsitz nahm. Er verkaufte einen Teil der zum Besitz gehörenden Güter an die Reichsstadt Reutlingen. Nachdem Ulrichs Sohn Konrad 1372 den Rest der Pfandschaft an Württemberg zurückgab, entstanden erhebliche Auseinandersetzungen mit Reutlingen, das Ansprüche auf die Burg stellte. Die Reichsstädter bemächtigten sich 1388 im Städtekrieg Gönningens und zerstörten die Stöffelburg. Nach der Schlacht bei Döffingen (1388) wurden im folgenden Jahr die besetzten Güter an Württemberg zurückgegeben und Reutlingen verzichtete auf alle Rechte. Danach blieb die Burg dem Zerfall überlassen. Mulden und überwachsene Schutthügel sind heute die einzigen Zeugnisse dieser ehemals stattlichen Anlage.

Die Stöffelburg zählt mit einer Länge von etwa 320 m und einer Breite von 60 m zu den größten Burganlagen der Schwäbischen Alb. Bei einer Grabung fand der Burgenforscher Konrad Albert Koch im Frühjahr 1930 Grundmauern und bei der von ihm als später bezeichneten östlichen Burg noch einen zerstörten kleinen Gewölbekeller. Anhand der Grundrisse vermutete er zwei zeitlich aufeinanderfolgende Burgen, was auch nun durch die Oberflächenfunde von  Christoph Bizer bestätigt wurde. Auf einem nach Westen gerichteten Sporn des Stöffelbergs gelegen, durchschneiden insgesamt 7 Quergräben den Fels. Bei der Burg an der Spornspitze trennt ein tiefer Graben die von einer Ringmauer umgebene Anlage mit Bergfried (6,9 x 7,3 m), Eckturm, Palas und einem weiteren Gebäude von der Vorburg. Die Burgfläche bildet in etwa einen Viertelkreis. Die Vorburg ohne Ummauerung besteht nur aus Hofraum. Nach Norden grenzt ein Seitengraben mit Wall die Burg ab.
 
An diese Burg aus dem 12. Jahrhundert schließt sich die spätestens im nachfolgenden Jahrhundert erbaute hintere Burg an. Die rechteckige Hauptburg - 42 m lang und 25 breit - wurde teilweise von einer Schildmauer umgeben. Ein Palas mit 5 Räumen dürfte als Wohnbebauung gedient haben. Der 5,9 x 6,2 m große über Eck gestellte Bergfried weist eine Mauerstärke von 1,9 m auf. Vorgelagert ist eine spitze dreieckig angelegte Vorburg. Ein Frontturm und mehrere Gräben sicherten die Anlage nach Osten ab.