Etter abitur i 1915, tjenestegjorde Heines som frivillig i første verdenskrig, og ble i 1918 dimittert som løytnant. Has innsats ble belønnet med Jernkorset klasse 2. I de første årene etter krigen var han med i frikorpset Roßbach og var i 1919 med i kamper i Baltikum og i 1920 i kappkuppet. I juni samme år skal han ha deltatt i drapet på Willi Schmidt, en 20 år gammel landarbeider.
I 1922 ble han medlem av NSDAP og i SA da Frikorps Roßbach gikk inn i SA.
I november 1923 deltok han i ølkjellerkuppet og ble dømt til 15 måneders fengsel. Han sonte i Landsberg fengsel samtidig med Hitler, og ble løslatt allerede i september 1924. På dette tidspunktet var NSDAP og SA forbudte organisasjoner, og han trådte da inn i Münchner Frontbann-Regiment, en dekkorganisasjon for SA. han trådte inn igjen i NSDAP og SA da disse ble tillatt igjen i 1925. Året etter hadde han graden av Standartenführer.
I 1927 ble drapet på Schmidt kjent og Heines ble anklaget. Saken kom opp i Stettin i april og mail 1928 og han ble dømt til 15 år i tukthus. Ankesaken i februar og mars 1929 endte med at han ble løslatt mot 5 000 reichsmark i kausjon. Samme år ble han utnevnt til leder av NSDAP for et distrikt i Oberpfalz for en kort periode. I 1930 ble han medlem av Riksdagen for Liegnitz. I årene 1931 til 1934 var han SA-leder i Schlesien og var samtidig Ernst Röhms nestkommanderende. I 1933 ble han medlem av statsrådet i Preussen og i mai samme år ble han leder av politiet i Breslau.
Henrettelsen
Hitlers sjåfør Erich Kempka hevdet i 1946 i et intervju at Edmund Heines ble funnet i seng med en uidentifisert 18 år gammel mann da han ble arrestert under De lange knivers natt, men han hadde imidlertid ikke selv observert dette. Ifølge Kempka, nektet Heines å samarbeide og ville ikke kle på seg. Da SS-folkene rapporterte dette til Hitler, hadde han personlig gått til Heines' rom og beordret ham til å kle på seg innen fem minutter, eller risikere å bli skutt. Etter at disse fem minuttene hadde gått, hadde Heines fortsatt ikke etterfulgt ordren. Som følge av dette, ble Hitler så rasende at han beordret SS-mennene å ta Heines og gutten på utsiden av huset og skyte dem.[4] Heines, Röhm og en rekke andre SA-leder ble fraktet til Stadelheim-fengselet i München, ca. 50 km nord for Bad Wiessee ved innsjøen Tegernsee hvor de ble arrestert, og henrettet samme dag. Hitler omtalte Heines som «en av de ledende medlemmene av en liten gruppe av elementer som holdt sammen gjennom lik legning» i sin tale i Reichstag 13. juli 1934.
