Chairman Donald McGauchie said Trujillo and the Telstra board agreed that now was a suitable time for a transition to a new CEO given the company's transformation is "well advanced and on track".

Telstra will now commence a search for a replacement with a new CEO expected to start on or around June 30.

McGauchie congratulated Trujillo on his achievements during his four-year tender.

"Under Sol's leadership, Telstra has significantly outperformed the market and its global peers, producing world-leading results within the telecommunications sector," he said, adding the Next G mobile network is Trujillo's "crowning achievement".

Trujillo said he would continue to drive the business until his departure and work with the board to prepare a smooth transition.