Waltersdorf ist ein typisches deutsches Angerdorf in Ost-West-Richtung. Die Gründungsurkunde ging schon im 15. Jh. verloren. Am 2. September 1355 wurde Waltersdorf erstmals urkundlich erwähnt. Lokator und erster Schulze war Ditmar de Waltheri Villa, und von diesem Namen „Waltheri Villa“ dürfte sich der Name des Dorfes abgeleitet haben.

Auch wenn Waltersdorf während des Hungerkrieges 141 kaum Schäden davongetragen haben dürfte, wird das Dorf in den Unruhen des Städtekrieges 1454 – 1466 unter dem Durchzug der verschiedensten Soldatenhaufen gelitten haben. Nach Beendigung dieses Krieges wurde Waltersdorf an einen Söldnerführer verpfändet, konnte jedoch 1487 von den Dorfbewohnern freigekauft werden. Im Reiterkrieg hatte Waltersdorf dann zwischen 1519 und 1521 unter Brandschatzungen zu leiden.

Am 27. Januar 1601 schlossen sich die Waltersdorfer Bauern zu einer interessanten Versicherung zusammen, den Waltersdorfer Vergleich. Danach verpflichteten sich die Dorfbewohner, Abgebrannten oder in großem Umfang Bestohlenen mit Baumaterial und Saatgut zu versorgen sowie beim Wiederaufbau zu unterstützen.

Die Kirche in Waltersdorf auf einer kleinen Anhöhe des Dorfangers mitten im Dorf ist ein Bau aus der 1. Hälfte des 14. Jhs. erstmals urkundlich erwähnt 1412. Das Kirchenschiff wurde aus Feldsteinen mit Backsteinecken aufgemauert, wobei man die Fenster und Türen mit Ziegeln umrahmte. Das Langhaus wurde um die Wende vom 14. zum 15. Jh. um einen Chor und eine südliche Vorhalle ergänzt. Ein 30 Meter hoher Turm auf der Westseite kam 1537 hinzu. In ihm hingen bis zum 1. Weltkrieg noch zwei Glocken von 1495, die sich vorher vermutlich in einem abseitsstehenden Holzgerüst befanden. Sie wurden wohl kriegsbedingt zur Rohstoffgewinnung eingeschmolzen. Eine Sakristei befindet sich nördlich des Kirchenschiffs. Chor und südliches Seitenschiff erhielten zu Beginn des 16. Jhs. massive Gewölbe.

Als ein Teil der wohl weitgehend verlorenen Ausstattung sollen sich Fragmente des Waltersdorfer Flügelaltars in einer Kirche in Allenstein befinden.

In der Ordenszeit wurde 1455 ein Pfarrer Martin erwähnt. Ab 1481 übernahm Pfarrer Nikolaus Roszenau die Pfarrstelle. Der während der Reformationszeit von 1521 – 1539 amtierende Pfarrer Jacob Westhoff war es vermutlich, der die Gemeinde in die evangelische Glaubensrichtung überführte.

In den Kämpfen des 2. Weltkriegs brannte die Kirche mit dem schönen Ostgiebel, der während eines Sturms 1982 einstürzte, vollständig aus, die Decken stürzten ein. Der Turm wurde am 7. März 1961 vom Blitz getroffen und eingeäschert. Die Sakristei ist noch erkennbar und der alte Taufstein aus Granit aus dem 15. Jh. ist noch vorhanden. Ein Einwohner rettete 1976 einen der schönen gotischen Rippensteine für das Heimatmuseum in Burgdorf. In der südlichen Vorhalle wurde eine Kapelle eingerichtet.

Im Jahr 1939 hatte Waltersdorf noch 471 Einwohner. Das sind, sicher bedingt durch die Nähe zur Grenze nach Nordostpreußen, die durch die nördliche Omazaschlucht verläuft, heute wesentlich weniger. In der Omazaschlucht existiert noch der Teufelsstein.

Eine Schule gab es in Waltersdorf bereits im 16. Jh. Jedenfalls wurde 1575 ein Schulmeister aktenkundig, weil er den Katechismus nicht beherrschte und deshalb verpflichtet wurde, diesen innerhalb von 4 Wochen auswendig zu lernen. Ab der zweiten Hälfte des 17. Jhs. sind etliche Lehrer bekannt. Die Schule war ab 1856 zweizügig. Das Schulhaus mit 2 Klassenräumen entstand 1909/10. Letzter Lehrer und Kantor bis 1945 war Paul Matern (1893 – 1980), während der Einberufungszeit im 2. Weltkrieg vertreten durch den Pensionär Kantowski aus Königsberg. Nach dem Krieg diente die Schule bis 1976 noch dem Schulunterricht, danach wurde sie kommerziell genutzt.

Den seit der Ordenszeit bestehenden Dorfkrug erwarb 1936 Arthur Pohl und gliederte diesem eine Kolonialwarenhandlung an. Am 18. März 1945 wurde das Dorf von der Roten Armee vereinnahmt. In der Nachkriegszeit ist der Dorfkrug verschwunden, ebenso wie etliche Bauerngehöfte. Im Ort ließen sich viele Ukrainer nieder.

Eine detaillierte Darstellung von Waltersdorf, insbesondere der Kirche, findet sich in den Heimatblättern des Kreises Heiligenbeil von Mai 1983, S. 522 ff und Mai 1984, S. 8 ff.