In 2006, Australia Post CIO Wayne Saunders was charged with a complete overhaul of the organisation's information technology.
Replacing its siloed, legacy systems was one problem. Another was that he couldn't remove full-time staff from the government-owned organisation.
Four years on, Australia Post still has some 900 IT staff, but their roles have changed.
Contractors were replaced with skilled staff who were "impregnated" into various teams.
And project management skills became vital as the company worked with external suppliers and integrators to implement and upgrade systems.
"We can't sack people in Post; it just doesn't happen," Saunders told attendees of a Gartner event in Sydney this week.
"You either have to convince people that they are no longer relevant and it is in their best interest to move on, or find a way to move them to another part of the organisation whilst we rebuild our skills."
Business process changes, training and development initiatives allowed Australia Post to free up staff from business-as-usual tasks to special projects and innovation.
Between 350 and 400 of Australia Post's IT staff currently work on business-as-usual functions - a far cry from the 800 staff required in 2006.
Saunders claims the IT unit has become more agile, responsive and effective by focusing on project management internally and relying on external subject matter expertise.
He said the transformation project hinged on communication between all stakeholders. Included were sceptics who had noted that the organisation's last major IT investment - during the Y2K era - did not pay off.
"When I arrived, Australia Post was still profitable ... [but] all the trends from around the world were showing that there was a cliff edge coming," he said.
"There were a lot of sceptics there; the first 12 months was about creating a dialogue about what do you want to look like, going forward.
"We had to rebuild the IT organisation as well as rebuild the technology and confidence in business."
While it was a "delight" to see the transformation occur, Saunders said the project might have been improved by establishing dedicated staff to manage business process changes.
Those staff should have left their day jobs, he said, and the team should have been refreshed every year to circulate expertise and stave off fatigue.
Looking forward, Saunders said Australia Post would invest in improving its customer service and loyalty, in much the same was as frequent flyer programs recognised passengers.