Nellenburg was een tot de Oostenrijkse Kreits behorend landgraafschap binnen het Heilige Roomse Rijk. De Nellenburg is nu nog een burchtruïne ten westen van Stockach in Baden-Württemberg. Het landgraafschap Nellenburg werd gerekend tot Voor-Oostenrijk.
De graven van Nellenburg zijn waarschijnlijk verwant met de hertogen van de Alamannen, die in 746 hun macht verloren. Graaf Eberhard III van Nellenburg stichtte in 1049 het beroemde Benedictijner klooster Allerheiligen in Schaffhausen. Op zijn laatst in 1256 verenigden de graven het ambt van graaf in de Hegau met hun huisbezit. Sindsdien noemen ze zich graaf van Nellenburg en landgraaf in de Hegau.
Na het uitsterven van de graven van Veringen in 1422 kwamen zowel het graafschap Nellenburg als het landgraafschap in de Hegau aan de heren van Tengen-Egislau. Deze verkochten het bezit in 1465 aan het aartshertogdom Oostenrijk. Toen deze gebeurtenis plaatsvond, is de von Nellenburg tak, naar het noorden van Duitsland vertrokken. Hier bezit de familie nog steeds een afgelegen landgoed.
Volgens artikel 8 van de Vrede van Presburg met het Eerste Franse Keizerrijk van 26 december 1805 moest Oostenrijk het landgraafschap afstaan aan het keurvorstendom Württemberg.
In het grensverdrag van Parijs dat op 2 oktober 1810 werd gesloten tussen het koninkrijk Württemberg en het groothertogdom Baden werd het voormalige landgraafschap Nellenburg aan Baden afgestaan.