With some analysts predicting that rivals such as Dell will use Fiorina's departure as an opportunity to win customers from HP, and others arguing that the company is in dire need of fresh direction, the job is a big challenge. Still, industry observers and CEO recruiters have plenty of suggestions on who would make good candidates.
Here are some of the names popping up:
Michael Capellas: The former CEO of Compaq sold his company to HP in mid-2002. In November 2003, he resigned from HP to head up MCI.
Capellas may soon find himself without a job if he is able to sell MCI to another telecommunications company.
"I think the world of Michael Capellas," said a former Compaq director. "He's a good operations guy and can fit in well with the HP culture, or any corporate culture."
Bringing back an executive who left after promising to stay at the company following the merger, however, could be a nightmare for image consultants.
"Although he is good at operations, HP's board may have a public-relations issue if they hire Capellas," said Stephen Mader, vice-chairman of executive search company Christian & Timbers. "Capellas is the guy that sold them the problems they are having."
John Joyce: Joyce is head of IBM's Global Services Division -- and HP views services as a high-growth area for the company, one where HP has been striving to improve its operations. In the past, Joyce also served as IBM's chief financial officer and as the company's president of Asia-Pacific operations.
Joyce would also have to wait some time to take over the CEO spot at IBM. CEO Sam Palmisano is only in his early 50s.
"I would also look at John Joyce from IBM, where he's been running a huge business for them," said David Nosal, a CEO search consultant.
"What better way to take on IBM than to hire an IBMer?" said Meta Group analyst Nick Gall.
Other strong IBM candidates include Steve Mills, senior vice-president of the software group; Abby Kohnstamm, senior vice-president of marketing; Nick Donofrio, senior vice-president of technology and manufacturing; and Doug Elix, senior vice-president of sales and distribution. Most have been at IBM for decades.
Whoever gets the top seat at HP, they have a big job to refocus the HP staff from internal silo building to customer service. As a long standing HP reseller Partner i can say they HP have become a joke to work with - no one takes any responsibility,no one has a broad knowledge of their own operations and everyone knows only their own little bit of turf. Its very frustrating when i know more about HP than they do. Outsourcing their Technical Support to India is the worse thing they have done - the knowledge level is appalling.