Heinzendorf ist das Dorf eines Heinz (Kurzname für Heinrich). Die Schreibweise ist im 14. Jahrhundert: „hainczendorf, Haynczendorf, Heinczendorf", im 15. Jahrhundert: „hanczendorff", im 16. Jahrhundert „Hantzendorf, Hanntzendorf, Haintzndorff, haintzendorf, handtzendorff", im 17. Jahrhundert „Haintzendorff, Hantzendorff", seitdem „Hainzendorf" und „Heinzendorf".
Heinzendorf gehörte zu den Iglauer Stadtgründen. In den Iglauer Losungsregistem erscheint Heinzendorf von 1425 bis 1616 mit sieben Besitzern. Im Jahr 1425 werden genannt: 1. Hanns „gener gesellonis" (Schwiegersohn des Gesell, seit 1428 Wenzeslaus gener gsellonis und später ein Steffi Gesell.) 2. Michel Setzer (seczer). 3. Peschl Jenikauer. 4. Nicolaus Heinzmani de Puschhofen (Nicolaus der Sohn des Heinzmann aus Puschhofen, einer Ortschaft südlich von Iglau). 5. Nicolaus filius Michaelis (der Sohn des Michel). 6. Hanns (und Johann) Hainczendorffer und 7. Michael de Przibislauia, statt seiner seit 1429 die Familie Kremser (Cremzer, Michel Cremser, Wenncz kremsar, Valtan Krembser, Mattl Kremser).
Im 16. Jahrhundert findet man die Familiennamen: Brosl, Pable, Jacob, Matausch, Proksch (Proksch Mattl), Kremser, Herman und Neubauer. Im Jahr 1668 wurden genannt: 1. Georg Lang, 2. der Schneider, 3. Proksch Model, 4. Siemandl Koscher, 5. Veith Neu Wirth, 6. der Schneller, 7. Thoma Ielg. Im Jahr 1778 verzeichnete das Grundbuch:
Nr. 1 Filipp Teltscher mit 275 M 11 mß Ausmaß.
Nr. 2 Andres Teltscher mit 310 M ll 3 /4 mß.
Nr. 3 Mathes Schneller mit 259 M 5 mß.
Nr. 4 Martin Schneller kein Grundbesitz.
Nr. 5 Gemeindehirtenhaus.
Nr. 6 Jakob Teltscher mit 162 M 12V4 mß.
Nr. 7 Georg Kütler mit 162 M IV4 mß.
Nr. 8 Georg Schneller mit 219 M 53/4 mß.
Nr. 9 Paul Boudalek mit 162 M 11V4 mß.
Die Gemeinde hatte UM 6V2 mß und drei Überländer aus Birnbaumhof hatten einige Metzen (Johann Brawenz 11 mß, Wenzl Teltscher 2 M IOV4 mß, Paul Teltscher 3 M 6V2 mß). Das Gesamtausmaß betrug 1577 M I5V2 mß.
Wie Birnbaumhof und Misching war auch Heinzendorf früher zu Böhmen gehörig. Seit dem Jahr 1509 führte es seine Steuerabgaben nach Mähren ab und erst seit 1750 ist es zu Mähren eingegliedert. In der bösen Zeit des Dreißigjährigen Krieges hatte Heinzendorf arg zu leiden. Eine Iglauer Amtsraittung aus dem Jahr 1630 verzeichnet dort drei öde Höfe und vier Untertanen (Menschen, die einer Grundherrschaft oder einem Landesherrn unterstanden). Am 26. Februar 1646 haben die Schweden, die die Festung Iglau besetzt hielten, das Dorf niedergebrannt.
In der Mitte des 18. Jahrhunderts (1750) waren drei Heinzendorfer Bauern verpflichtet, jede Woche drei Tage vierspännige Ochsenzugrobot zu leisten, ein Bauer jede Woche drei Tage dreispännig zu roboten und zwei Bauern wöchentlich zweimal zweispännige Robot (unbezahlte Pflichtarbeit für den Grundherrn) zu leisten. Robotgeld zahlten im Jahr 1754 Gregor Schneller 5 fl. (Gulden, auch Florin genannt, eine historische Geldeinheit) 30 kr. (Kreuzer, eine kleinere historische Geldeinheit), Martin Rackezek, Martin Töltscher, Johann Töltscher und Jacob Kettler je 2 fl. 30 kr. Das Robotablösungskapital im Jahr 1848 betrug 1165 fl. 28 kr.
Die Gemarkungsfläche von Heinzendorf beträgt 544 ha; der Ort ist eine selbstständige Gemeinde. Alle zwölf Gemeinderäte waren 1939 Tschechen. Schule und Post waren in Helenental, die Pfarre in Iglau, die Bahnstation Beranau (G Iglau) und die Gendarmerie in Groß-Beranau. — Zu Heinzendorf gehören auch die Holymühle und das Jägerhaus im Spitalwald.
Der deutsche Besitz im Jahr 1945 war folgender:
Nr. 6 Franz Achatzi, 44,00 ha.
Nr. 7 Laurenz Pollak, 16,40 ha.
Nr. 9 Johann Pollierer, 28,00 ha.
Nr. 15 Franz Neubauer, 20,00 ha.
Nr. 18 Franz Pertlik, 0,80 ha.
Nr. 40 Mathias Neubauer, 0,50 ha.
Nr. 41 Paul Neubauer, 1,00 ha. Karl Low Erben, 402,00 ha.