Die Nelson-Mandela-Schule Staatliche Internationale Schule Berlin wurde im Jahr 2000 vom Berliner Senat als Internationale bilinguale (Englisch/Deutsch) Gesamtschule mit Grundstufe und gymnasialer Oberstufe gegründet. Sie wurde bis zum Schuljahr 2003/2004 bis zur 9. Klasse ausgebaut. In den ersten beiden Jahren nach ihrer Gründung war die Schule in der Curtiusstraße in Zehlendorf untergebracht, bis sie im Sommer 2002 ihr Domizil in der Pfalzburger Straße 23 beziehen konnte.
Der Oberschulcampus war zunächst in der ehemaligen Robert-Bosch-Schule in der Kastanienallee 12-13 in Charlottenburg-Westend untergebracht, bevor er 2013 in die Pfalzburger Straße 30 umzog.
Die Nelson-Mandela-Schule ist Mitglied im European Council of International Schools. Ihren Namen hat die Schule von Nelson Mandela (*18.06.1918), welcher einer der führenden Anti-Apartheid-Kämpfer Südafrikas und der erste schwarze Präsident des Landes war. Er gilt als einer der wichtigsten Vertreter im Kampf gegen die weltweite Unterdrückung von schwarzen Menschen sowie als Wegbereiter des versöhnlichen Übergangs von der Apartheid zu einem gleichheitsorientierten, demokratischen Südafrika.
Die Grundstufe befindet sich in einem fünfgeschossigen und zweiflügeligen Altbaukomplex an der Pfalzburger Straße 23. 1989 bis 2002 war in dem Gebäude die Robert-Jungk-Gesamtschule untergebracht.
Am 25.01.2008 eröffneten Baustadtrat Klaus-Dieter Gröhler und Schulstadtrat Reinhard Naumann das Richtfest für einen Ergänzungsbau für die Schule, am 08.10.2008 wurde der Schlüssel übergeben.
Am 18.09.2014 unterzeichnete Schulleiter Christian Nitschke im Beisein von Bezirksbürgermeister Reinhard Naumann in Peking gemeinsam mit seiner Kollegin Xue Lixa von der Dong Zhimen High School feierlich einen Freundschaftsvertrag, mit dem eine deutsch-chinesische Schulpartnerschaft begründet wurde. Beide Schulen wollen den pädagogischen Austausch der Lehrkräfte sowie Austauschprogramme und Sprachkurse für die Schülerinnen und Schüler beider Schulen fördern und entwickeln.
