A year to the day that HP’s last CTO Shane Robison vacated the premises, the first big wheel at the company to depart after Meg Whitman took over – with Meg saying he wouldn’t be replaced – she changed her mind and tapped Martin Fink to fill the empty slot.

Fink also gets to be director of HP Labs, replacing Prith Banerjee, who left in April.

Fink was lately head of HP’s embattled Business Critical Server (BCS) unit, which suffered Oracle’s desertion until it forced Oracle to continue to write software for its Itanium machines. Oracle quoted Fink as saying Intel would slap “high fives all around” if it thought it could shut down Itanium manufacturing since HP is practically its only customer. HP told a different story.

Before the BCS gig, Fink ran HP’s Open Source and Linux operation. Ric Lewis will now run BCS on an interim basis. Interim HP labs chief Chandrakant Patel has been named an HP Senior Fellow and the Labs’ chief engineer. He will report to Fink, HP said, to “ensure the right marriage of innovation with the business units, work on how to evolve the CTO model and continue his research in end-to-end design and management of HP infrastructure systems.”

Fink in turn will report to Meg.

HP’s announcement says Fink is supposed to “work closely with HP’s strategy teams to drive and accelerate the innovation agenda for the company. As part of his role, Fink will be responsible for looking holistically at how innovation is created and commercialized at HP.”

Meg figures Fink’s “experience on the front lines with customers combined with his experience in the business units will be invaluable as we work to focus our innovation agenda at HP. Martin will ensure that our research and development activity is aligned with our steady focus of anticipating and delivering on the future needs of our customers.”

The company spent $3.3 billion on HP Labs in its 2011 fiscal year, up from $2.8 billion a couple of years before. That’s about 2.5% of sales. Meg wants less pure research and more marketable goods unlike the fabled memristor widgetry.

Fink has been at HP since 1985.