On 29 April 1940, Stahlecker arrived in Oslo, Norway, where he held various posts, most notably as commander of about 200 Einsatzgruppe members of the Security Police and SD. He was promoted to SS-Oberführer. He was succeeded in this position in autumn 1940 by Heinrich Fehlis.
In June 1941, Einsatzgruppe A followed Army Group North and operated in the Baltic states and areas of Russia up to Leningrad. Its mission was to hunt down and annihilate the Jews, Gypsies, Communists, and other "undesirables". In a 15 October 1941 report, Stahlecker repeatedly emphasized the following point: "Native anti-Semitic forces were induced to start pogroms against Jews during the first hours after capture [German occupation]." In the introductory part of the report he wrote, "though this inducement proved to be very difficult [emphasis added]." Further on in the report, while describing the events in Lithuania, he touched on the point again: "This [local involvement in the killings] was achieved for the first time by partisan activities in Kovno. To our surprise it was not easy at first to set in motion an extensive pogrom against Jews [emphasis added]. Klimatis [sic], the leader of the partisan unit... who was primarily used for this purpose, succeeded in starting a pogrom on the basis of advice given to him by a small advanced detachment acting in Kovno, and in such a way that no German order or German instigation was noticed from the outside." By winter 1941, Stahlecker reported to Berlin that Einsatzgruppe A had murdered some 249,420 Jews. He was made Higher SS and Police Leader (German: Höhere SS- und Polizeiführer, HSSPF) of Reichskommissariat Ostland, which included Estonia, Latvia, Lithuania and Belarus, at the end of November 1941. Stahlecker was killed in action on 23 March 1942, in a clash with Soviet partisans near Krasnogvardeysk, Russia.Heinz Jost then assumed command of Einsatzgruppe A.