Microsoft’s (Nasdaq: MSFT) newly appointed Chief Executive Officer Satya Nadella, in an effort to reignite growth, is shuffling management and putting former political operative Mark Penn in the new role of chief strategy officer.

Tony Bates, who was passed over for the CEO job, is leaving the company, with Eric Rudder, the head of advanced strategy, taking over his duties on an interim basis, Microsoft said Monday in a memo to employees. Tami Reller, the executive vice president in charge of marketing, is also leaving and being replaced by Chief Marketing Officer Chris Capossela.

The shakeup is the most extensive yet for Nadella, who was named CEO in February after a five-month search and is tasked with speeding up a turnaround at the world’s biggest software maker. He’ll be leaning on a former political strategist in Penn, who worked on Hillary Clinton’s failed 2008 presidential bid. More recently, Penn, 60, developed Microsoft’s “Don’t Get Scroogled” advertising campaign, a political-style attack on Google Inc.

“He’s aggressive,” Mark Moerdler, an analyst at Sanford C. Bernstein & Co., said of Penn. “Maybe this will add a little testosterone to the organization to counter the fact that Satya is more of a deep thinker.”

Penn’s background is in public relations — he spent six years as CEO of Burson-Marsteller. His aggressive style puts him at odds with some managers, who were uncomfortable with the Scroogled campaign, said people with knowledge of the matter.

(The memo followed a report by Bloomberg earlier Monday about the changes.)

Super Bowl Ad

He’s also helped develop less controversial ads like Microsoft’s first national Super Bowl commercial this year. In the ad, former football player Steve Gleason, who suffers from amyotrophic lateral sclerosis (ALS) and can’t speak, narrated using Microsoft technology.

“His focus on using data to quickly evaluate and evolve our campaigns has driven new insights and understanding,” Nadella said in the memo.

Part of Penn’s job will involve helping the company decide where to invest, and he will join the product leadership team, said a person with knowledge of the change.

The overhaul follows last month’s announcement that hardware group chief Julie Larson-Green will move to the applications and services unit. Thom Gruhler, a vice president who oversaw Windows and Windows Phone marketing, will lead marketing for the applications and services group, people with knowledge of the matter said. Reller notified employees of that change in an e-mail, they said.

Mobile Laggard

Microsoft shares fell 1.4 percent to $37.78 at the close in New York. The stock has risen 3.9 percent since Nadella’s appointment on Feb. 4, and has trailed the Standard & Poor’s 500 Index in three of the past four years.

Nadella, a 22-year Microsoft veteran, is the company’s third CEO after Bill Gates and Steve Ballmer. He’s charged with accelerating expansion at a company that hasn’t seen sales growth exceed 6 percent since 2011. Microsoft’s investments in mobile haven’t put a dent in Google and Apple Inc.’s control of the smartphone market, while cloud applications from competitors pose an increasing threat to Microsoft’s flagship Windows business.

“Nadella is trying things out,” said Moerdler, who has the equivalent of a buy rating on Microsoft. He said he expects additional changes in senior leadership, including possible outside hires.

Job Split

Bates was among the leading internal candidates for the top job, along with Nadella and Chief Operating Officer Kevin Turner. Bates, a former Cisco Systems Inc. executive, ran Microsoft’s Skype unit before becoming an executive vice president in July. He doesn’t have another job lined up and plans to take some time to figure out his next move, said a person familiar with his plans.

Reller, who joined Microsoft in 2001, was also promoted to executive vice president in July and led marketing for the Windows 8 operating system. Capossela had been named chief marketing officer back in 2011, though his role was reduced in July when Ballmer split marketing between Reller and Penn, with the latter taking on advertising strategy.

Penn’s ties to the Clintons date back to the 1990s and his work in the re-election campaign for President Bill Clinton. He worked on Hillary Clinton’s campaign until April 2008, when he came under fire for his firm’s role in promoting trade with Colombia.

At Microsoft, Penn has a longstanding relationship with Ballmer and Gates and advised the company during its antitrust case with the U.S. government.