Der kleinste Ort der Marktgemeinde Staatz blickt wie die anderen Katastralgemeinden auf eine lange Geschichte zurück. Waltersdorf wird 1169 zum ersten Mal urkundlich erwähnt. Die Bauern waren stets Untertanen der Burg- und später der Schlossherren von Staatz.
Der Ort besitzt eine kleine Kapelle, die 1858 zu Ehren des hl. Kilian errichtet wurde.
Eine eigene Volksschule bestand bis 1969.
Einst war Waltersdorf eine eigenständige Gemeinde. Doch seit der Gemeindezusammenlegung 1966 richten sich nun alle Interessen wieder nach Staatz.
Waltersdorf verfügt, man möchte es kaum glauben, über den höchsten Punkt der Marktgemeinde. Der „Haltersteig“ (der Grenzweg zu Hörersdorf), überragt den Staatzer Berg sogar um über 20 Meter.
Zu erreichen ist er über die Trift, eine idyllische Kellergasse.
Dann geht es in den Wald bis an die hochgelegene Gemeindegrenze.