Walther Stahlecker nacque il 10 ottobre 1900 a Sternenfels in Austria da Eugen Stahlecker, un insegnante, e da Anna Zaiser. Frequentò il Ginnasio a Tubinga laureandosi poi in legge nel 1927. Si sposò nel 1932 con Louise-Gabriele Frein von Gültlingen dalla quale ebbe quattro figli
In quello stesso anno si iscrisse al Partito Nazista (tessera n. 3219015) e alle SS (tessera n. 73 041).
Tra il 1933 ed il 1937 lavorò nella polizia politica del Wüttenberg divenendone capo nel 1934.
Nel 1938 entrò nei servizi di sicurezza delle SS (SD) divenendo capo dei servizi di sicurezza del "Distretto Danubio" (Vienna). Promosso Standartenführer divenne capo della polizia e delle SS nel protettorato di Boemia e Moravia. Nel 1940 venne inviato a Oslo in Norvegia dove ricoprì lo stesso incarico.
Il 22 giugno 1941 - promosso a Brigadeführer - venne messo a capo dell'Einsatzgruppe A incaricato di "ripulire" dagli ebrei i Paesi Baltici e l'Area settentrionale dell'Unione Sovietica.
Nel novembre 1941 venne nominato comandante della Polizia di Sicurezza e delle SS del Reichkommissariat Ostland che riuniva Lettonia, Lituania, Estonia e Bielorussia.
Morì il 23 marzo 1942 dopo essere stato ferito a Krasnogwardeisk in uno scontro con i partigiani russi.