Heines participó en la Primera Guerra Mundial como Kriegsfreiwilliger, siendo desmovilizado en 1918 con el rango de teniente. Entre 1919 y 1922 fue líder de una unidad perteneciente al Freikorps Roßbach. Después de asesinar a un obrero en 1920, hubo de huir hacia el sur.
Estando en Múnich, en diciembre de 1922 se afilió al Partido Nacionalsocialista y a su milicia, las Sturmabteilung (SA). Tras el fracaso del Putsch de Múnich, en noviembre de 1923, Heines fue detenido y estuvo encarcelado durante varios meses, siendo liberado en 1924. Tras su reingreso a las SA, en pocos años fue ascendiendo por la estructura del movimiento nazi y en 1926 ya había ascendido al rango de SA-Standartenführer. Sin embargo, también se forjó una terrible reputación entre sus opositores. El diario socialdemócrata Vorwärts lo definió en 1928 como "uno de los peores fenómenos durante el período de Hitler en Múnich".[6] En 1929 fue condenado a una pena de cárcel por el asesinato del comunista Conrad Pietrzuch, que había sido golpeado hasta la muerte por una banda de matones de las SA liderada por Heines. El juicio tuvo que ser repetido por una cuestión técnica, y Heines pronto recibió una amnistía debido a los supuestos motivos "patrióticos" que llevaron al asesinato de Pietrzuch.[7]
En las elecciones generales de 1930 fue elegido diputado por el Reichstag. En 1931 se convirtió en adjunto del líder de las SA, Ernst Röhm —lo que le da un enorme poder—, y también en líder de las SA en Silesia. El 12 de mayo de 1932 Heines protagonizó un incidente cuando, acompañado de otros SA, asaltó al periodista Helmuth Klotz en el restaurante del Reichstag.[8] Klotz había desertado del Partido Nazi al SPD y unos meses antes había publicado unas cartas de Röhm de fuerte temática homosexual.[9]
Tras el nombramiento de Adolf Hitler como canciller y la toma del poder por los nazis, el 26 de marzo de 1933 Heines fue nombrado jefe de policía de Breslau; además, dicho puesto le hizo responsable del Campo de concentración de Breslau-Dürrgoy, el cual Heines llegó a casi a convertir en una auténtica propiedad privada.[10] Entre sus primeras víctimas se encontraron los socialdemócratas, y particularmente Paul Löbe, antiguo presidente del Reichstag, al que Heines hizo que secuestraran sus hombres (sin conocimiento siquiera de la Gestapo y las autoridades nazis) en venganza porque Löbe lo había excluido del parlamento en 1932.[11]
A finales de junio de 1934 Hitler le comunicó a los líderes de las SA que se reunieran en la ciudad balneario de Bad Wiessee, donde unos días después se encontrarían con él para celebrar un encuentro. En realidad, aquello era una trampa tramada por Hitler y sus principales colaboradores con la que esperaban descabezar a las SA de una vez por todas, lo que posteriormente se llamaría «Noche de los cuchillos largos». Al amanecer del 30 de junio, columnas motorizadas de policías, SS y agentes de la Gestapo llegaron a Bad Wiessee,[12] acompañadas del propio Hitler. Según Erich Kempka, uno de los hombres presentes en la redada, las SS encontraron a Heines en la cama, con un soldado de las SA de 18 años. Goebbels haría hincapié en estos datos en la propaganda posterior para justificar la purga como un golpe a la inmoralidad.[13] Heines sería inmediatamente detenido, llevado a la Prisión Stadelheim, y poco después fusilado junto a otros líderes de las SA.
