Die Burg zum Stein findet erstmals in Lagerbüchern des 14. Jahrhunderts Erwähnung und wird dort als „domus“ (Haus) oder „domicilium“ (Wohnsitz) eines „Hainrich vom Stain“ genannt. Unter den nachfolgenden Besitzern wird das Haus noch bis ins 16. Jahrhundert hinein als Burg bezeichnet. Oben genannter Hainrich war Angehöriger des weit verzweigten niederadeligen Geschlechts „vom Stein“, das ursprünglich aus der Gegend um Marchtal an der Donau stammte und von dem sich offenbar im 13. Jahrhundert ein Zweig in Cannstatt niederließ. Im näheren Umfeld Cannstatts ist dieser Zweig erstmals im Jahr 1258, in Cannstatt und im Dunstkreis der dort ansässigen niederadeligen Geschlechter seit 1271 fassbar.
Bezeichnend für die Nähe zum Grafenhaus ist der Umstand, dass gleich mehrere Vertreter des Zweiges in zahlreichen Urkunden der Grafen von Württemberg aus der zweiten Hälfte des 13. Jahrhunderts als Zeugen bzw. Bürgen erscheinen und dort unter anderem als „ritter dienzman grave Eberhartez von Wirtenberch“ aufgeführt werden. Bereits gegen Ende des 14. Jahrhunderts starb der Cannstatter Zweig derer „vom Stein“ jedoch aus. Wie das Geschlecht an die Rechte der Burg gelangte, ist unbekannt. Angesichts der offenkundigen Nähe zu den Grafen von Württemberg, ist denkbar, dass dies über eben jene im Laufe des 13. Jahrhunderts geschah.
Der Standort der Burg zum Stein und ihr einstiges Aussehen lassen sich nur noch ansatzweise über topografische und archäologische Anhaltspunkte ermitteln: Der Verlauf des Burggrabens scheint sich noch auf einer Karte von 1823 in der Anordnung der umliegenden Gebäude und den Grundstücksgrenzen widerzuspiegeln. Dabei wird auch deutlich, dass der Graben einst vom Sulzbach gespeist worden sein könnte. Beim Neubau der Häuser Spreuergasse 37 und 43 in den 1960er Jahren zeigte sich der Graben als trogförmiger Sohlegraben von über 4,8 Meter Breite und ca. 1,60 Meter Tiefe. Im unteren Bereich des Grabens, nur wenige Zentimeter über der Sohle, fanden sich die Bruchstücke einer Bügelkanne der rotbemalten schwäbischen Feinware aus dem 13. Jahrhundert. Aus den jüngsten Schichten der Grabenverfüllung stammen hingegen einige Bruchstücke der jüngeren grauen Drehscheibenware, die zeitlich ins 14./15. Jahrhundert einzuordnen sind. Darüber hinaus wurden aus der Verfüllung Lederreste sowie zugespitzte Holzstäbchen entnommen, die womöglich als Schäfte von Armbrustbolzen zu interpretieren, jedoch heute nicht mehr erhalten sind.
Insgesamt korrelieren die Funde aus der Grabenverfüllung gut mit der von den Schriftquellen überlieferten Nutzungsgeschichte der Burg. Da Cannstatt in den „Annales Sindelfingenses“ unter den Orten aufgeführt ist, die 1287 von Rudolf I. eingenommen wurden, darf angenommen werden, dass die Burg zum Stein zu den Burgen zählte, die er in diesem Zuge brechen ließ. Den eingangs genannten Quellen nach zu urteilen, wurde sie jedoch – wenn auch weniger wehrhaft – wiederhergestellt.
Im Zentrum des Burgareals ist ein Burghügel bzw. -plateau von rund 30 Meter Durchmesser anzunehmen, auf dem vermutlich ein Wohnturm stand, der noch auf der Duttenhofer’schen Karte von 1816 in Form eines quadratischen Baukörpers wiedergegeben sein könnte. Letzte Reste dieses Turms hatten sich im Keller des in den 1950er Jahren abgebrochenen Vorgängergebäudes der heutigen Spreuergasse 37 erhalten. Dieser wies Plänen aus den Jahren 1944/45 und 1951 zufolge einen quadratischen Grundriss von 9,2 x 9,0 bis 9,1 Meter mit ca. 1,3 bis 1,4 Meter starken Mauern auf, wobei die nördliche Kellermauer zu einem unbekannten Zeitpunkt entfernt wurde. Demnach ist die Burg zum Stein als Turmburg mit einem zentralen Wohnturm anzusprechen, wobei offenbleiben muss, ob es sich um eine regelrechte Motte mit künstlich aufgeschüttetem Burghügel handelte.
Bemerkenswert ist die zentrale Lage der Burg im Nordosten der spätmittelalterlichen Altstadt unweit der Stadtkirche und unmittelbar nördlich des Esslinger und Konstanzer Hofes. Diese zwei Höfe waren, wie Analogien zu anderen Orten nahelegen, vermutlich Teile eines zu einem unbekannten Zeitpunkt geteilten Fronhofes, der mutmaßlich auf den alamannischen Herzogshof in Cannstatt zurückzuführen ist. Im 13. Jahrhundert erscheinen die zwei Teile des Hofes im Besitz der Grafen von Württemberg und der Grafen von Grüningen-Landau. Wie die Württemberger an diesen Hof gelangten, ist unklar – ursprünglich handelte es sich hierbei wohl um Reichsgut. Die Übernahme des Hofes dürfte jedoch einen wesentlichen Schritt im Rahmen der Herrschaftserschließung des Cannstatter Raumes durch die Württemberger im 13. Jahrhundert darstellen. Nicht zuletzt befand sich an diesem Herrschaftsmittelpunkt seit der zweiten Hälfte des 13. Jahrhunderts auch das Landgericht der Grafen von Württemberg. Die Errichtung der Burg zum Stein und ihrer Vergabe an ein den Württembergern nahestehendes Adelsgeschlecht, ist dabei als materieller Ausdruck dieser Erschließungsprozesse zu betrachten.