On the minus side, Mills wasn't CEO at the time, Scavo said. "He didn't lead that, he participated, but it's still an interesting choice."

In addition, Mills only gained control of IBM's hardware business last year, giving him less experience in that arena than software.

This aside, "Steve is definitely CEO material," said analyst Ray Wang, CEO of Constellation Research.

"He's actually one of the best managers in the business. He's managed their mergers and acquisition strategy and has done a good job of aligning those with industries and back to services," Wang added.

However, "I don't know if it's likely for him to go to HP," Wang said. "They'd have to try really hard to bring him aboard, given they've been fierce competitors."