REDMOND, Wash.— Microsoft Corp.’s annual executive retreat is an exclusive affair for company bigwigs—180 with the title of distinguished engineer, corporate vice president or higher—and a rare opportunity to plot strategy and socialize with bosses who could green light projects and advance careers.
Satya Nadella decided to shake things up. At last year’s meeting, the first he fully planned after taking over as chief executive officer in 2014, he broke with tradition by inviting new chiefs of companies Microsoft had recently acquired, according to an executive who attended.
Some Microsoft senior leaders complained to Mr. Nadella, saying the new hands didn’t have the titles or tenure to attend the two-day event at Suncadia Resort, a mountain getaway 80 miles east of Seattle. Their presence breached the protocol established by Microsoft’s two former CEOs, Bill Gates and Steve Ballmer. Another half dozen newcomers attended this spring.
In response to one executive, Mr. Nadella said, “We’re doing this because of the insights they bring.”
Mr. Nadella’s point was clear. The tech world has left Microsoft’s desktop far behind, and the 41-year-old software giant, which has struggled against more-nimble rivals such as Apple Inc. and Alphabet Inc.’s Google, has to shed its “not invented here” bias and overwhelming focus on engineering.
Under Mr. Nadella, Microsoft is shaping up to be the only pre-internet tech giant to escape the decline of its legacy product—the Windows PC operating system—and emerge as a leader in the new era of cloud computing.
Mobile devices and web-based, on-demand computing have diminished one-time titans such as Intel Corp. and International Business Machines Corp. Even early internet giants Yahoo Inc. and AOL Inc. have been unable to keep pace with the shift to mobile computing.
Microsoft’s transformation has been bumpy as the new culture clashed with the old. Some longtime employees said the legacy was being disrespected. Newcomers weren’t shy about challenging their way of thinking.
Its insular atmosphere long stifled new hires who came up through the ranks of other companies. These days, acquired companies’ CEOs are given freedom to point out failing strategies and are running workshops for executives on innovation, and the company is embracing open source, once regarded as a “cancer.”
“We did not get everything right about our culture, especially around learning from others,” Mr. Nadella said in an interview. “Otherwise, why would we miss big trends?”
New voices from acquisitions adding to Microsoft’s decision-making include Javier Soltero of mobile email and calendar app maker Acompli, Chad Fowler of task-management mobile app Wunderlist and Nat Friedman of Xamarin, a maker of open-source software development tools.
These are among the executives from the 36 major acquisitions Mr. Nadella completed in his first 2½ years as CEO—almost triple the 13 Mr. Ballmer made in the previous 2½ years.
Microsoft closed the largest purchase in its history last week, a $26.2 billion deal for the professional social network, LinkedIn Corp. Mr. Nadella aims to extend the reach of Office products and its Dynamics business software with LinkedIn’s professional networking, the company said.
LinkedIn also brings executives with experience building a popular web service, something Microsoft has struggled for years to do. “The culture he’s trying to create is very aligned with LinkedIn,” said the company’s CEO, Jeff Weiner, who plans to continue in his role after the acquisition.
Mr. Nadella is himself an insider, a 24-year veteran of Microsoft, originally from Hyderabad, India, who worked his way up through online services, business software and cloud computing, which provides web-based computing power and storage.
The company’s history is littered with deals that failed because the company was intent on promoting its own products instead of offering customers what they wanted. Billions of dollars evaporated following the purchases of Nokia’s handset business, bought to boost its mobile operating system, and digital advertising giant aQuantive, picked up to help Microsoft’s efforts in that area.
With deep roots in engineering, Microsoft built products more often than buying them. “When they did buy, it was because of a grumbling self-acknowledgment that they were behind in some technology,” said Ray Ozzie, who served as Microsoft’s chief software architect after it bought his collaboration software startup in 2005.
Mr. Ozzie left Microsoft in 2010 and founded another startup that developed collaboration technology, this time for mobile, which Microsoft bought last year. He said Mr. Nadella recognizes “that Microsoft doesn’t have a birthright to win in every category.”
During Mr. Ballmer’s CEO tenure, from 2000 to 2014, annual profit grew to $22.07 billion from $9.42 billion, and revenue soared to $86.83 billion from $22.96 billion. But sales of the Windows PC operating system steadily declined and now account for less than 20% of the company’s total revenue, from roughly 33% in 2002, and the stock price was stagnant.
“An absolute, utter crisis is a much easier tool to use to galvanize change,” Mr. Nadella said.
Besides Apple and Google in mobile computing, Microsoft faced competition from companies such as Salesforce.com Inc. and Amazon Web Services, which pioneered new businesses in on-demand access to software and computing power. The cloud-based services threaten Microsoft’s legacy software products, which customers license to install on their own computers.
Mr. Nadella snapped up Revolution Analytics and Metanautix to help cloud-computing customers make sense of the giant amount of data they accumulate. He bought Sunrise Atelier and VoloMetrix to add mobile calendar features and email analytics tools to its cloud-based Office 365. He bolstered Microsoft’s security offerings with Secure Islands and Adallom.
Revenue from commercial sales of Office 365 jumped 54% in the latest fiscal year ended June 30. Azure, Microsoft’s cloud-computing service, more than doubled sales in the period, although it is still one-fifth the size of Amazon Web Services, according to research firm Gartner Inc.
The Office business segment and server units, fed by the cloud-based products, have grown in importance as Windows has slipped. Office, which includes word-processing, email and spreadsheet software as well as other collaboration applications such as SharePoint and Lync, accounted for nearly 28% of Microsoft’s sales in the latest fiscal year. Server products and tools, which include Azure as well as corporate applications that companies run on their own servers, generated more than 22% of Microsoft’s sales.
“In three years, they have turned from the backwater of IT to being front and center,” said Aaron Levie, CEO of cloud-storage company Box Inc., which both partners and competes with Microsoft.
The stock price hit an all-time high of $62.98 on Dec. 13, about 17 years after climbing to its previous high-water mark. Shares closed Thursday at $62.58.
Mr. Soltero, who joined Microsoft after it bought Acompli in late 2014, has been an internal advocate for change. “Sometimes I feel like I’m just running around Redmond carrying a mirror,” forcing a close examination of products and methods, he said. “Let’s be very, very, very, clear about what we’re good at and what we’re not.”
Acompli developed an email and calendar app for Microsoft Outlook users on smartphones using Apple’s iOS and Google’s Android—platforms Microsoft had previously dismissed as it tried to build a mobile franchise with its own Windows operating system.
Mr. Nadella soon put Mr. Soltero in charge of the entire Outlook business, one of Microsoft’s most widely used products. Last month, he promoted Mr. Soltero again, to oversee product strategy for the Office group, which includes Word, Excel and PowerPoint as well as the Skype messaging and Yammer collaboration services.
“In the past, Microsoft assumed you had to be at the company 10 or 20 years to be in a leadership role,” said Scott Guthrie, executive vice president of the Microsoft Cloud and Enterprise Group, who joined the company in 1997. “We consciously have recognized, ‘No, actually, that’s wrong.’ We want to have people that have only been here six months.”
It hasn’t always gone smoothly. In January 2015, a few weeks after joining the company, Mr. Soltero had harsh words for Office group employees about Microsoft’s complacency.
“Nobody was lamenting the absence of Outlook on the iPhone or on Android prior to us delivering that product,” Mr. Soltero said he told several hundred employees in the Microsoft Executive Briefing Center and a few thousand more watching online. “There was a deafening silence in the room,” he said.
In one PowerPoint presentation a year after he joined, he pressed employees to not rest on past success in email software. Microsoft’s Outlook held more than 60% of the corporate email market in the mid-2000s, according to the research firm Radicati Group. These days, corporate email has migrated to web services, and users can read email on mobile devices. In that larger market Microsoft has weakened to have about a 55% share, according to International Data Corp.
“The opportunity is huge and really ours to lose,” he said he told the group. “If we continue on our current course and speed, we will become this”—he showed a slide with a sad face on top of the logo of Lotus Notes, a now faded email program that dominated in the 1980s.
“It was meant to be a daring call to action,” Mr. Soltero said. He received emails accusing him of being “disrespectful of the legacy” of the company. “I think the suggestion that we weren’t winning was a painful one for them to hear,” Mr. Soltero said.
He said employees who didn’t buy in to the new way of thinking “self-selected” out of the Outlook group. He said he didn’t know if they found other jobs at Microsoft or left the company.
Microsoft extended its reach into devices that don’t run Windows by buying Xamarin, the San Francisco maker of open-source software tools, in February. The tools let developers skilled with Microsoft’s C# programming language make products for Apple and Android operating systems, as well as Windows.
Former CEO Mr. Ballmer had derided open-source software, which is shared freely and whose programming instructions can be viewed, modified and distributed by anyone, in a 2001 newspaper interview as “a cancer,” since it competes with Microsoft’s software.
The landscape has since shifted: open-source software is widespread, and if developers can’t use Microsoft products to create programs for the most popular platforms, rival programs are readily available.
Mr. Ballmer, Microsoft’s largest individual shareholder, said earlier this year his position has evolved and that he “loved” seeing the March announcement that the company would sell a version of its SQL Server database software that is compatible with Linux, a leading open-source operating system.
Mr. Nadella promoted Xamarin’s CEO, Mr. Friedman, to corporate vice president of mobile-developer tools, a top job in the business that serves coders.
“I feel like I get to be a touchstone for open source,” Mr. Friedman said, adding he has used his connections in the open-source world and Silicon Valley to help Microsoft.
Shortly after Microsoft acquired the German startup behind task-management mobile app Wunderlist in June 2015, Qi Lu, a Nadella lieutenant at the time, met with chief technology officer Mr. Fowler. The Microsoft executive asked him to describe how he would build Office if he were able to start from scratch.
“I rattled off a bunch of things off the top of my head…things that we would have said over and over at Wunderlist and had baked into our culture,” said Mr. Fowler, who now manages the product at Microsoft.
He talked about rapidly updating software rather than long-term product cycles. He mentioned real-time synchronization between the services that run on the web and the apps that run on mobile devices, since customers have that expectation. And he said applications, when users launch them, need to start immediately.
Mr. Lu asked him to put his ideas on paper and shared them widely in the company. He also asked Mr. Fowler to address a staff meeting with thousands of employees and run workshops for executives to explain his thinking.
“There’s a thin line between hubris and confidence,” Mr. Nadella said. “I want us to be more on the confidence side.”
Write to Jay Greene at Jay.Greene@wsj.com