Der Ortsteil Steinstücken entstand 1787, als Bauern aus Stolpe Land außerhalb ihrer Dorfgrenzen erwarben. Dort entwickelte sich im 19. Jahrhundert eine kleine Siedlung. Stolpe wurde nach Berlin-Wannsee eingemeindet. Eine Reform von 1868 ordnete Grundstücke außerhalb des Wohnorts der Besitzer steuerlich und rechtlich der Gemeinde zu, in der der Eigentümer wohnte. Bei der Gründung Groß-Berlins 1920 gelangte Steinstücken so zu Berlin, obwohl es außerhalb der eigentlichen Stadtgrenze lag.
Bis zum Kriegsende 1945 war das kaum von Bedeutung. Verwaltet von Berlin, war das Leben der Einwohner mehr nach Potsdam ausgerichtet. Doch kam die Straßenreinigung aus Wannsee und als die Alliierten die Teilung nach den Kehrgrenzen vornahmen, lag Steinstücken als Teil des US Sektors im eigentlichen sowjetischen Sektor.
Bis zum 18. Oktober 1951 gab es kaum Probleme. Doch an diesem Tag erklärte die DDR einseitig, dass der Ort nun zur DDR gehören würde. Volkspolizisten besetzten den Ort. Da sich die Bewohner an die US Militärbehörden wandten, machte die DDR-Regierung schnell einen Rückzieher. Doch war der Ort nun von Potsdam und Babelsberg durch eine Postenreihe abgetrennt. Der Weg nach Westberlin führte über einen Waldweg und zwei Grenzübergänge.
Am 1. Juni 1952 verbot die DDR allen West-Berlinern das Betreten der DDR, mit Ausnahme Ostberlins, und errichtete Straßensperren.
Der Mauerbau 1961 machte Steinstücken für einige Zeit zur Fluchtinsel, denn die Ortsgrenze war zunächst nur mit spanischen Reitern für Fahrzeuge blockiert. Nachdem rund zwei Dutzend Grenzsoldaten geflohen waren, wurde auch Steinstücken von der DDR durch eine eigene Mauer eingeschlossen. Strom und Leitungswasser kamen trotzdem weiter aus der DDR.
Um Steinstücken zu sichern, wurde ein ständiger US-Militärposten von drei Mann in der Exklave eingerichtet. Die Soldaten wurden per Hubschrauber eingeflogen, wofür extra ein Landeplatz mit Beleuchtung angelegt wurde. Auch die Ablösung erfolgte auf dem Luftweg. Flüchtlinge wurden ebenfalls mit dem Hubschrauber ausgeflogen.
1963 wurde Steinstückens Landverbindung nach Wannsee durch weitere Mauerstücke unterbrochen. Die Versorgung erfolgte teils auf dem Luftweg. Der Zugang für die rund 200 Einwohner war nur über einen gut 1 km langen Verbindungsweg möglich. An beiden Enden gab es ein Tor mit Posten. Alle Besucher, auch Lieferanten, mussten eine Meldebescheinigung über einen Zweitwohnsitz in Steinstücken vorweisen.
Das Einfliegen des Weihnachtsmanns war jedes Jahr eine Meldung in Zeitungen und Berliner Abendschau wert. Erst am 3. September 1971 gab es eine Lösung. Das Viermächte-Abkommen sah vor, dass „die Probleme der kleinen Enklaven, einschließlich Steinstückens ….. Durch Gebietsaustausch gelöst werden“. Da jede Änderung der Stadtgrenze den Viermächtestatus berührte, war solch eine Vereinbarung zwischen den vier Nationen notwendig. Ein gesondertes Abkommen zwischen West-Berlin und der DDR vom 20. Dezember 1971 regelte die Details: Ostberlin trat einen 20 Meter breiten und 900 m langen Streifen zwischen Steinstücken und Kohlhasenbrück an West-Berlin ab. Die DDR erhielt im Gegenzug eine unbewohnte Exklave in der Nähe, die zu Wannsee gehörte. Damit war Steinstücken endlich keine Exklave mehr. Da der Ort beidseitig von der Mauer umgeben war, kamen Touristen und Westberliner in Scharen. Es führte sogar eine BVG Buslinie in den Ort. Die Versorgung mit Energie und Wasser wurde nach und nach auf Belieferung aus West-Berlin umgestellt. Im Jahr des Mauerfalls 1989 bezogen aber noch immer zwölf Häuser Wasser aus dem Potsdamer DDR-Netz.
Und es blieben Streitpunkte. Bis zum Mauerfall waren die Grundstücke in der Steinstraße (Südrand), der Rote-Kreuz-Straße (Westrand) und dem westlichen Teil der Stahnsdorfer Straße (Nordrand) nicht direkt erreichbar. Die Mauer stieß unmittelbar an die Grundstücksgrenzen, aber die Bürgersteige gehörten zur DDR, die eine Benutzung verweigerte. Auf den privaten Grundstücken der Steinstraße entstand ein asphaltierter Weg, den die Betroffenen benutzen durften.
Der Mauerfall 1989 brachte den Einwohnern nicht nur die Befreiung von der Mauer – ohne diese war die Exklave kein Touristenziel mehr. Von der Mauer blieb nur ein einziges Segment. Der Berliner Mauerweg spart Steinstücken aus. Gelegentlich besuchen ehemalige US Soldaten den Ort, am ehemaligen Hubschrauberlandeplatz steht ein Denkmal aus zwei Rotorblättern.
