In Urkunden finden sich schon früh Hinweise auf das „Dorf, wo Nussbäume wachsen“: 1114 Nuzdof, 1324 Nuzdorf am Nuzperig, auf dem Nuzbach. Der Name des Ortes Nußdorf leitet sich von den dort zahlreiche wachsenden Walnussbäumen und Haselnusssträuchern ab.
Der ursprüngliche Ortskern, der am ehesten einer mittelalterlichen Dorfstruktur entspricht, dürfte die Greinergasse mit den Einmündungen der Hammerschmidt- und der Sickenberggasse sowie der Kahlenberger Straße sein (T-förmiges Straßendorf).
1819 wurde die Nußdorfer Brauerei errichtet und die Kahlenbergbahn auf den Kahlenberg machte Nußdorf im 19. Jahrhundert zu einem beliebten Ausflugsziel der Wiener. Auch die Bevölkerung von Nußdorf wuchs rasch an. 1795 bestand der Ort aus 109 Häusern mit 865 Einwohnern, 1808 lebten bereits 1.265 Menschen in 120 Häusern. Lebten 1832 in 152 Häusern noch 1.503 Menschen, so waren es 1890 bereits 5.191 Einwohner.