Elop, 51, came to Microsoft as part of the deal unveiled in 2013 to buy the mobile phone unit of the Finland-based tech group.
It was the second stint at Microsoft for the Canadian national, hired as chief executive by Nokia in 2010 in a bid to revitalize the group's smartphone efforts.
At one point, Elop had been rumored as a potential candidate for CEO at Microsoft.
In the shakeup announced by Microsoft CEO Satya Nadella, Elop will be replaced as head of the firm's "Windows and Devices Group" by Terry Myerson.
More From This Section
"We are aligning our engineering efforts and capabilities to deliver on our strategy and, in particular, our three core ambitions," said Nadella.
"This change will enable us to deliver better products and services that our customers love at a more rapid pace."
Microsoft has failed to get much traction for its Windows Phone platform even with the acquisition of Nokia. A survey by IDC said Windows was expected to capture just 3.2 percent of the global smartphone market this year.
Also leaving in the reorganization are two executive vice presidents, Kirill Tatarinov and Eric Rudder, who with Elop will depart "after a designated transition period," the statement said.