The company said the change was effective as of Tuesday, when the board made its final decision to ask Fiorina to step down. Robert Wayman, HP's chief financial officer, has been named interim CEO and has been appointed to the board. Patricia Dunn, who has served on the board since 1998, has been named chairman.
ZDNet Australia spoke this morning with local HP corporate manager Steven Reece, who declined to comment on Fiorina's departure apart from saying that HP would continue to meet the needs of its customers in the region.
Fiorina's severance package is US$21.1 million, a sum that includes stock options and a cash payment based on her salary and bonus, said HP spokeswoman Monica Sarkar.
According to the company, the departure stemmed from disagreements over how to execute the company's strategy.
"The differences came down to Carly catalysing the transformation of HP. She did that in remarkable fashion and executed the merger with Compaq in superior fashion. But looking forward, we think we'll (need a CEO with) hands-on execution," Dunn said on a conference call.
Dunn said that the board had been discussing Fiorina's performance for several weeks and had sought outside advisers -- including longtime counsel Larry Sonsini -- to help the directors make their decision. She added that no single event had triggered her departure.
Fiorina acknowledged discord with the company's board.
"While I regret the board and I have differences about how to execute HP's strategy, I respect their decision," Fiorina said in a statement.
Fiorina is eligible for a normal severance package from the company, Wayman said.
HP is scheduled to report its fiscal first-quarter results on February 16. The company said Wednesday that results will be in line with expectations.
The departure of Fiorina, who arrived at the company in 1999 from Lucent Technologies, comes as HP struggles to achieve consistent growth in its financial performance, particularly in its enterprise group. The company reorganised last month, combining its PC and printer units.
Fiorina has resisted calls to break HP, a Silicon Valley icon, into two separate companies, with one focused on business customers and another focused on consumers.
HP's merger with Compaq Computer, which was spearheaded by Fiorina, has also been criticised. Although the merged company has managed to wring out costs by combining operations, it has lost market share in certain areas, according to analysts.
Just two weeks ago, HP denied reports that it was planning to redistribute some of Fiorina's day-to-day responsibilities.
Walter Hewlett, a former HP director and son of a company co-founder, said in a phone interview that he was surprised by the decision.
"I know she's been under a certain amount of criticism, but (this) is somewhat unexpected," said Hewlett, who led an unsuccessful proxy battle to defeat HP's acquisition of Compaq. "I believed her when she said she had an excellent relationship with the board."
Hewlett also said he believed the board would give Fiorina much more time to execute on the merger, which was completed in 2002.
"I didn't expect the board to act so soon," he said.
Fiorina's departure is the second change for the HP board this week. On Monday, Sanford Litvack resigned as a director and was replaced by venture capitalist and former board member Thomas Perkins.
HP plans to launch a search for a permanent CEO. Wayman said on the conference call that he expects to step back into his CFO role once a new chief executive is found.
Wayman and Dunn said that the company intends to stick to its "portfolio" strategy of selling a broad range of products and services.
The company has acknowledged that it considered spinning off its printer business at least twice in the past but decided against it.
"We think it is a unique portfolio, one that is stronger together than apart," said Wayman.
Analysts said that Fiorina's departure clears the way for the dramatic possibility of splitting the company in two, with the printer/PC unit becoming its own entity.
"The decision opens up the possibility, which was really off the table before, that the new management will re-examine the possibility of possibly partitioning the company, which we view as positive for the stock," said Richard Chu, an analyst at SG Cowen.
Regardless of whether the company does split, HP still needs to address the challenge of marketing itself as both an enterprise company and consumer one, analysts said.
"To be selling iPods out one door and on the other side helping Procter & Gamble manage its IT infrastructure -- it doesn't seem like it can come together for one company, unless you're running a conglomerate" like General Electric, said Chris Foster, an analyst with Technology Business Research.
HP will likely begin trying to address the message and company vision, said Frank Gillett, an analyst with Forrester Research.
"Strategically, HP is (at) an interesting crossroads," said Gillett. He noted that its competitors IBM and Dell have clear business strategies, while Sun Microsystems has been reinvigorated after struggling for the last few years.
CNET News.com's Dawn Kawamoto and John G. Spooner contributed to this report.
