Heinrich Freiherr von Zedlitz war ein Sohn des Kammerherrn und Schlosshauptmanns Hugo Freiherr von Zedlitz (1816–1893) und der Ellen von Zedlitz, geborene Cowell (1835–1912).
Schon als Primaner interessierte er sich für die junge nationale Bewegung in der Studentenschaft und trat deshalb zu Beginn seines Jurastudiums 1882 dem VDSt Berlin bei. Dort sehr aktiv wurde im Wintersemester 1884/85 der Vorsitz des VDSt übertragen. Gleichzeitig wurde er in den Berliner Studentenausschuss gewählt. Dort kam es zu heftigen Auseinandersetzungen mit dem Ausschußmitglied Alfred Oehlke über die Teilnahme des Dichters Julius Wolff (1834–1910) am Reichsgründungskommers des VDSt Berlin am 18. Januar 1884.
Dies resultierte in einer Duell-Forderung Oehlkes an drei Ausschussmitglieder, darunter Zedlitz und Richard Holzapfel (1862–1885). Das Duell am 5. Januar 1885 sorgte reichsweit für Aufsehen. Während der Kugelwechsel Zedlitz-Oehlke unblutig endete, wurde Holzapfel im folgenden Duell getötet. In der anschließenden Schwurgerichtsverhandlung wurde Zedlitz freigesprochen, obwohl er sich als „schuldig“ bekannt hatte.
Im Jahr 1885 diente Zedlitz als Einjährig-Freiwilliger beim 5. Jäger-Bataillon in Görlitz. Als Referendar war er am Amtsgericht Muskau, darauf beim Amtsgericht Neurode und dann im Landgericht I Berlin tätig. Am 30. Juni 1888 wurde er zur Regierung nach Bromberg versetzt. Er bestand als Regierungsreferendar am 30. Mai 1891 die zweite Prüfung für den höheren Verwaltungsdienst und wurde zum Regierungsassessor ernannt. Als solcher wurde er 1891 der königlichen Regierung in Osnabrück zugeteilt und am 1. Juli 1894 an das königliche Oberpräsidium in Hannover versetzt. Vom Sommer 1897 an war er Landrat in der westpreußischen Kleinstadt Konitz. Dort brachen infolge des Mordes an einem Gymnasiasten 1900 die schwersten antisemitischen Unruhen im wilhelminischen Kaiserreich aus.