Fue el octavo de diez niños del maestro sastre Friedrich Stephan (1792-1860), quien fue concejal municipal en Stolp, y de Marie Luise Weber Döring (1794–1869).
En 1865, sugirió utilizar tarjetas postales en Alemania, las cuales fueron introducidas después de que el canciller Otto von Bismarck lo ascendió en 1870.
También se le acredita haber introducido el teléfono en Alemania.
Hasta el año 1891, Heinrich von Stephan fue su presidente.
Stephan falleció en 1897 en Berlín, después de haber hecho un profundo impacto en la estandarización del servicio postal en todo el mundo.