Der Name der Burg – in den frühesten Nennungen um 1100 „Wirtinisberk“ und „Wirtineberc“ – ist wahrscheinlich auf die häufig vorkommende keltische Ortsbezeichnung „Virodunum“ zurückzuführen. Dieser alten Ortsbezeichnung wurde dann ein germanisches „Berg“ als Grundwort angefügt, die Burg wurde nach dem Berg benannt, auf dem sie errichtet wurde. Dieser Befund eines hallstattzeitlichen Ursprungs des Namens wird gestützt durch zahlreiche keltische Ortsbezeichnungen und -namen in der näheren Umgebung, darüber hinaus fügen sich auch archäologische Funde in Neckar- und Remstal in das Bild einer in keltischer Zeit eher dicht besiedelten Gegend ein. Da das aus dem Keltischen stammende Wort „-dunum“ eine Befestigung bezeichnet, könnte auch an der Stelle der Burg Württemberg eine keltische Höhensiedlung bestanden haben. Von dort, dem heute meist Rotenberg genannten Berg, sind allerdings keine vorgeschichtlichen Spuren bekannt, sie sind nach der umfassenden Umgestaltung des Burgplatzes von 1819 bis 1821 aber auch nicht mehr zu erwarten. Die ältere Vermutung, der Burgname könnte aus einer anderen Region, insbesondere aus Luxemburg, hierher übertragen worden sein, ist unwahrscheinlich und gilt als widerlegt. 1802 wurde die Schreibweise des Namens Württemberg in der heute geläufigen Form festgelegt, der Name für den Burgberg bzw. die verschwundene Burg wurde 1907 daran angepasst.
Die frühesten schriftlichen Erwähnungen des Namens sind meist schwierig zu datieren. Sie treten in der Zeit um 1100 erstmals auf und beziehen sich nicht auf die Burg selbst, sondern auf Familienmitglieder, die sich nach der Burg Württemberg, ihrem Sitz, benannten. Die wohl früheste dieser Zubenennungen stammt von 1092, als „Conradus de Wirtinisberk“ anlässlich eines Rechtsgeschäfts genannt wird.
Die Burg muss zu diesem Zeitpunkt bereits bestanden haben, wie nicht nur diese Zubenennung, sondern auch ein aus der Burg stammender, auf den 7. Februar 1083 datierter, allerdings unvollständig erhaltener Inschriftenstein zeigt. Er ist als Spolie in die Grabkapelle Königin Katharinas gelangt. Dieser Stein belegt die Weihe der Burgkapelle 1083 durch Bischof Adalbert von Worms und zeigt damit, dass der Bau der Burg zu diesem Zeitpunkt weitgehend abgeschlossen war. Die Inschrift lautet:
ANNO DOMINIC(A)E (I)NCARN(ATIONIS) MILLE(SIMO) LXXXIII INDIC(TIONE) V(I) VII IDUS FEB(RUARII) DED(ICATA) HEC CAP(ELLA) AB A(D)ELB(ERTO) WORMA(ATI)ENS(IS) EC(CLESIE) EP(ISCOP)O IN H(ONOREM) S(ANCTI) [NICOLAI]
Übersetzung: Im Jahr der Fleischwerdung des Herrn 1083, in der 6. Indiktion, am 7. Februar wurde diese Kapelle von Bischof Adalbert von Worms zu Ehren des heiligen Nikolaus geweiht.
Dass die Kapelle dem Heiligen Nikolaus geweiht war, ist zwar aus der Inschrift nicht mehr ersichtlich, aber aus anderen Quellen bekannt.
Der Berg, auf dem die Burg errichtet wurde, hat eine bevorzugte Lage über dem Neckartal: Rund zweihundert Meter erhebt sich der 411 Meter hohe Württemberg bzw. Rotenberg über das Flusstal und bietet einen weiten Blick über Cannstatt und in das Stuttgarter Tal.
Die Burg ist eng verbunden mit der frühen Geschichte des Hauses Württemberg, das sich im 11. und 12. Jahrhundert herausbildete. Dieses Geschlecht gehörte sehr wahrscheinlich zu den nahen Verwandten der salischen Könige und Kaiser und verfügte wie diese im 11. Jahrhundert über Besitz im Remstal. Zunächst nannten sich die späteren Württemberger nach Beutelsbach, dem Zentrum ihres Besitzes im Remstal. Auf dem dortigen Kappelberg errichteten sie wahrscheinlich im 11. Jahrhundert eine erste Burg, die aber zugunsten des neuen Sitzes aufgegeben wurde. Die frühen Württemberger reihten sich in die breite Front des schwäbischen Adels ein, die sich während des sogenannten „Investiturstreits“ gegen die salischen Herrscher stellten. Ihr Besitz im Remstal war jedoch von salischem Besitz und Verbündeten der Könige umgeben, die Burg Kappelberg hatte in dieser Hinsicht folglich keine günstige Lage.
Konrad von Beutelsbach, wie er in manchen Schriftquellen genannt wird, schuf deshalb im letzten Viertel des 11. Jahrhunderts einen neuen namengebenden Sitz für sich und sein Geschlecht und errichtete auf dem Württemberg, dem Neckartal zugewandt, eine neue Burg. Damit fügt sich die Adelsfamilie der Württemberger in das Bild des hohen Adels dieser Zeit ein, der an repräsentativen Orten neue Höhenburgen errichtete und sich nach diesen benannte. An diese Burgen wurden die Herrschaftsrechte der Familie gebunden, und aus einem breiter angelegten Familienverständnis entstand unter anderem durch die Betonung der männlichen Erbfolge und die Weitergabe der Zubenennung als Familienname das „Haus Württemberg“.
Zur Zeit ihrer Erbauung waren mit der Burg Württemberg wahrscheinlich nicht nur die Herrschafts- und Gerichtsrechte über die unmittelbar benachbarten Siedlungen wie beispielsweise Uhlbach sowie Unter- und Obertürkheim verbunden, sondern auch diejenigen über Cannstatt mit seinem wichtigen Neckarübergang. Die Siedlung Rotenberg, die über eine sehr kleine Markung verfügt, war seit etwa 1100 der Burgweiler der Burg Württemberg, könnte aber auch schon vor der Burg entstanden sein. Hier lebten im Hochmittelalter die Menschen, die zum Bauunterhalt und zur Hofhaltung benötigt wurden.
Zum Aussehen und zum Baubestand der Befestigung finden sich erst seit dem 16. Jahrhundert Hinweise in Verzeichnissen und Beschreibungen der württembergischen Verwaltung oder in wenigen frühen Darstellungen. Sie sind jedoch ungenau und dürftig. Erst im 18. Jahrhundert und vor allem Anfang des 19. Jahrhunderts wurden genauere Darstellungen und Grundrisse des Baubestands angefertigt. Sie zeigen eine wehrhafte, dem Gelände entsprechend beinahe kreisförmige Anlage mit drei mächtigen, mit vorgelagerten Gräben versehene Ringmauern. Die innere Ringmauer umschloss die eigentliche Burg mit Palas und Wirtschaftsgebäuden. Ein Bergfried, wie er in Burgen des 13. Jahrhunderts häufig anzutreffen ist, war nicht vorhanden. Lediglich kleinere Tortürme sicherten die Durchlässe der Ringmauern. Dieser altertümliche und doch wehrhafte Eindruck, den die Befestigung machte, bestärkt die Vermutung, dass der Grundbestand der Anlage mit Kernburg und drei Ringmauern sehr weit ins Mittelalter zurückreichte und in wesentlichen Teilen auf die Zeit der Erbauung um 1080/1083 zurückgehen könnten. Darauf deuten auch die Beschreibungen hin, die vor und um 1800 von der Burg entstanden.
Die Geschichte der Burg im Mittelalter lässt sich nur bruchstückhaft rekonstruieren. Zumindest bis um die Mitte des 13. Jahrhunderts diente sie wohl noch als Hauptsitz des Hauses Württemberg und wurde von unfreien Dienstleuten verwaltet, die sich bald ebenfalls nach ihr nannten. Im Reichskrieg König Heinrichs VII. gegen Graf Eberhard I. von Württemberg wurde die Burg 1311 eingenommen und zerstört, jedenfalls militärisch unbrauchbar gemacht; nach dem Friedensschluss 1316 ließ sie Graf Eberhard wiederherrichten, obwohl er das Zentrum seiner Herrschaft planvoll und dauerhaft nach Stuttgart verlegte. Auch für das 14. und 15. Jahrhundert gibt es bislang kein klares Bild vom Stellenwert der Burg. Sie blieb jedoch durchgehend bewohnt und sicher auch militärisch von gewisser Bedeutung – die konfliktbeladene Nachbarschaft zur Reichsstadt Esslingen spielte dabei eine Rolle. Im 15. Jahrhundert residierte hier neben dem Burgvogt zeitweise der württembergische Landhofmeister, der ranghöchste Beamte der Grafen bzw. Herzöge – meist ein adliger Diener –, was darauf hindeuten könnte, dass die Burg als Zubehör dieses Amtes betrachtet wurde und zeigt, dass sie weiterhin einen besonderen Rang einnahm und in gutem Stand gehalten wurde. Mit Lebensmitteln, Baumaterial und Holz wurde die Burg über Frondienste aus den umliegenden württembergischen Ämtern versorgt. Die Einwohner des Weilers Rotenberg hatten die Burg im Kriegsfall zu verteidigen.
1519, als der Schwäbische Bund gegen Herzog Ulrich ins Land zog, wurde die Burg besetzt. Nach ihrem Sieg zögerten die Eroberer nicht, das Symbol württembergischer Herrschaft in Brand zu stecken: „dasselb feur hat man durch das gantz lannd aus, dann das schloß hoch gelegen, gesehen“, berichtete der Kriegsschreiber des Schwäbischen Bundes. Nach der Rückkehr Herzog Ulrichs 1534 wurde die Burg zumindest teilweise wiederhergestellt und bewohnbar gemacht und wieder mit einer kleinen ständigen Besatzung von bis zu drei Mann versehen. 1554 wurden diese Burgwächter abgeschafft, dennoch wurden die Gebäude weiter instand gehalten. Das Wohnhaus des Burgvogts, die sogenannte Burgvogtei am äußeren Mauerring, später auch Jägerhaus genannt, blieb dauerhaft bewohnbar. Tore und Mauern wurden ebenso wie die wichtigen Gebäude laufend ausgebessert, aber der Charakter als Befestigung trat seit dem 16. Jahrhundert in den Hintergrund. Die Gräben wurden vermehrt als Obstgärten genutzt; gelegentlich wurden Gefangene von der Regierung hierhergebracht. Überlegungen während der Regierungszeit Herzog Carl Alexanders (1733-1737), die Burg zur modernen Festung auszubauen, gelangten jedoch nicht einmal zur detaillierten Planung.
Nach dem Dreißigjährigen Krieg, wahrscheinlich ab 1655, war auf der Burg eine „Hochwacht“ eingerichtet worden: Um Feuersbrünste zu verhindern, wurde von hier die Gegend weiträumig überwacht und bei einem Brand je nach Lokalisierung eine genau festgelegte Anzahl Kanonenschüsse abgefeuert. Diese Einrichtung, für die später auf dem Dach des Palas eine Plattform gebaut wurde, blieb noch bis 1851 bestehen – nach dem Bau der Grabkapelle hatte man für die Hochwacht ein eigenes Holzgerüst errichtet.
Schon früh wurde die Burg ein beliebtes Ausflugsziel. Von jeher hatten die meisten württembergischen Herzöge und ihr Hof die Burg zu bestimmten Anlässen oder zum Genuss der Aussicht aufgesucht. Besonders König Friedrich I. besuchte sie öfter und plante möglicherweise, sie umfassend renovieren zu lassen. Spätestens in seiner Regierungszeit begannen auch breitere Schichten, die Aussichtsplattform auf dem Württemberg aufzusuchen, wo der Burgvogt einen Ausschank betrieb. Die auf Veranlassung des Königs gezeichneten Grundrisse und die genauen Darstellungen des Kupferstechers August Seyffer aus dieser Zeit zeigen eine weitgehend gut erhaltene Burg, in der auch der Weihestein von 1083 an der Wand der Stallgebäude, des sogenannten Langen Baus, eingemauert war. Friedrichs Sohn und Nachfolger König Wilhelm I. jedoch ließ die Burg ab 1819 vollständig abtragen, um an ihrer Stelle die Grabkapelle für seine Gemahlin Katharina zu erbauen.