Leading an organisation that has undergone dramatic change in its ownership, been forced to address the challenges of a deregulated and fiercely competitive market, as well as deal with the demands and expectations of politicians, regulators and the wallets of the public, remains a challenge. CEO Solomon Trujillo's passion for telecommunications stand him in good stead as he seeks to completely change Telstra's business culture at high speed. By Jennifer Alexander

Q: What do you like best, and least, about your role?

A: I like being able to innovate, to create, to drive results, to define a business to a point where it's doing things nobody's ever done before and delighting customers and shareholders. It's a nice gig, as some would say. I least like dealing with the breaking down of regulatory or bureaucratic barriers; while all large companies have them, you always want your company to be as fast and nimble as any other.

Q: What are the particular challenges you face?

A: When I was recruited, the Telstra Board knew that the company needed a massive transformation, given its legacy as a branch of government that was privatised. So our challenge has been to change a culture, build a strategy and execute it to better compete in the marketplace. When I arrived, Telstra had a history, since competition was introduced, of losing market share and customers. My job was to rebuild the company under a core strategy and deliver results to shareholders and customers; naturally, they're very focused on results!.

Q: How will you define success?

A: The mark of success will be a company that has a set of capabilities unmatched in the Australian marketplace, and is a world-class business. World class measured by how shareholders would describe the returns that they receive, world class measured by customers and the choices they make with us, and world class in the context of employees that say, "You know, this is the best place to work and I'm engaged, I'm challenged and I love winning".

Q: You have 45,000 employees. How do you lead an organisation that's so large?

A: I'm a believer in the engaged-CEO model; to be engaged in just about everything. That doesn't mean you do people's jobs, but you're engaged in ensuring the strategy is right, engaged in ensuring that people are executing the strategy, engaged in communicating the strategy, engaged in holding people accountable for what they do, and engaged in allocating resources; obviously you're facing the customers and stakeholders, too. So engaged is an operative word. High energy is required, as is the ability to do something simple that I like to describe as the "think and do" principle; you have to be able to think, and you have to be able to do.

Q: You have been involved in beverages, banking and retail, but what's the allure in telecoms?

A: From the black phones and simple devices of 20–30 years ago, I don't think there's been a more dynamic industry than telecommunications. The myriad technologies, devices and software capabilities, all kinds of things: we package them, we integrate them and, guess what? We touch about every single individual in Australia's life today, and it's hard for me to imagine anything more significant or more rewarding than being involved in this industry.

Q: So the industry has a buzz for you?

A: The buzz is tied to the industry, but actually it's about the magnitude of the impact that it has. I like to describe Telstra in Australia as being the central nervous system of the economy; I can take you to any bank and show how we're basically carrying all the transactions they do. Or we can look at mining and see the dramatic changes in the technology used compared to 30 years ago. In education, I can show you kids in the bush who are now taking field trips to the Great Barrier Reef without actually being there. Or women now getting breast screening through mobile vans leveraging technologies that Telstra has created. There's so many ways that we can touch people's lives; to me that's exciting.

Q: Are you a techie?

A: I'm not a technoid, as some people describe themselves. I don't like to mess around and plug in wires and fix cars. But I love the idea of technology and what it can do in application. So, for example, I expect Telstra to be world class at applying technologies. The way that we apply them is to try to meet consumer needs. As such, I am always scanning for and looking at what the next technology might be, so that we can bring its utility to the consumer.

That's why you can see Telstra's transformation. While clearly, we are deploying technology faster than Telstra's ever done, we are also probably deploying it faster than any company in the world right now. We're delivering new services and new capabilities probably faster than anybody else.

I like to talk about it in terms of needs. As a business you have a need, as a consumer you have a need. The question is, how can that need be best met? And, as a business, how can we make money doing it?

Q: What skills are required to affect such a cultural change in order to achieve this?

A: Succeeding somebody as CEO in a steady business state is one thing. Going into a company and literally changing the tyres, engine and transmission while the car's moving down the road at 100 miles an hour is a whole different phenomenon. The skills required in lining a company with the right people and administering it are decisiveness, clarity of vision and a willingness to take risks.

Q: What do you look for in the people you appoint?

A: Again, I like the thinkers and doers. I love people who can think, conceptualise and imagine; and I love people that can actually go do things right. Lots of companies have had great strategies they couldn't execute because they didn't have the people who could implement them; and lots of companies have had great implementers who got left behind because they didn't have a strategy to take them further.

The one thing we're driving here at Telstra is a principles-based form of leadership. You see it in terms of how we deal with the government, how we deal with the regulator, how we deal with our customers, how we deal with our shareholders, how we deal internally with each other. There should be no surprises, it's all about our values and integrity.

Q: How did you learn to become a leader?

A: First, by experience. I've done about every job you can imagine. I've washed dishes, moved furniture and painted houses. You learn by function how to drive optimal performance. When I worked in a truck stop in the US, there were certain hours at night with a high inflow of people wanting to eat. The question was how to manage the volume. I used to sit there and say, "‘Okay, how many dishes can I wash in a shorter period of time and get 'em on the racks, onto the tables?' I used to challenge myself, not because somebody asked me to, I just wanted to. It was always ‘How can I make the process more efficient?'".

As a leader, you know there is a process like that for virtually every job and function. If the function has no value you should eliminate it.

Second, is the study of people. All my life I've looked at people and tried to look for the things I found were great attributes or that motivated me.

The last point of being a leader is about your value system; in how you think about things strategically, about your own unique principles. Part of this then is leading by example; I don't think I've ever asked an employee to do more than I would do myself.

Q: You've had role models?

A: Yes. And I tell you, you can learn both from people who are good and not-so-good role models. I probably learned more from those who were not so good because I saw the impact they had on staff when they took away all incentive, emotion and attraction of doing a job. As a CEO, I'm always looking at the people who have done terrific things, who have innovated.

Q: It is often said that we learn from our mistakes.

A: The best performers I've ever seen or worked with are people that have made mistakes. Making mistakes means you get to learn about balance or boundaries. It's part of what I tell our people in terms of product development and innovation; if we don't have a dud somewhere along the way, we're not good enough.

One thing that I have learned from mistakes in the past is, as a leader, sometimes you just have to cut and run; when you make choices on certain people for certain jobs, or you are following a strategy that isn't going to work, you've just got to move on. That's essentially what you're seeing here at Telstra; we are moving this company very fast.

Q: I'm aware that you coach people. Is that something you do naturally?

A: I love coaching people. It's interesting, early on in my career I was a guy determined to be a CEO. Once I was there all I cared about was what I did and how we got our results. But there's a point where you take more pleasure in seeing your own people achieve their success. I have a fundamental belief that most people underestimate what they're capable of, and sometimes it just takes some coaching to unlock their thinking.

I have a leadership-development program at Telstra that asks people to live with me for a period of time. I bring people in and I talk through things that are going on in my head; perhaps we've got a major transaction or a decision and I ask them to give me their thoughts on any trade-off issues, and so on.

This is all a part of coaching; if you ask enough questions of people, light bulbs go on. I'm a believer in letting people search for their own answers.

I'm also a big believer in diversity. I love the idea of having 100 per cent of the workforce in this company saying "You know what? If I want to have Sol's job, I know I have a shot at it". Now, they may not want my job, but if they do, whether they are man or woman, of certain beliefs or skin colour, it doesn't matter.

Q: As the first native white Hispanic American to serve as a CEO of a Fortune 150 company, how important was that breakthrough for you?

A: Put that way, it wasn't that important to me. Quite simply, I just wanted to be a CEO and lead a company. But sometimes, people need to see people like themselves in key roles; they need to know that by somebody having done it, they can. That's what diversity is about. In Telstra, for the first 90 years of its history, most of the CEOs were engineers; if I wasn't an engineer I would never have had a chance to be CEO. Well, guess what? All those paradigms are broken because I want 100 per cent of the workforce to be able to say, "If I perform, I have a shot to go wherever I want to go". That's what diversity is about, appreciating engineering skills versus marketing skills versus human resource skills versus financial skills. If we were all the same, we'd be boring.

Q: Diversity; how is Australia doing?

A: I do believe there is a need for more diversity. Globally, Australia is behind the rest of the world. When I walked into the Australian business community, in almost every meeting I went to I noticed there were no women.

And now we have a high percentage of our senior execs who are women. And it's not because I said, "I want a woman"; it's because we have people that needed the opportunity to show their talent.

Q: You've been CEO in three different continents, are there cultural differences in business?

A: I have lived in the US, London, Paris and now Australia, and I would say fundamentally there's not a lot of difference in that all of us are motivated by many of the same things. If you're in a business context, you like being successful; so the needs of people working in companies are not much different. The needs of consumers really aren't much different. People may speak a different language or have different customs, but do they change the business? No.

Q: There's only 24 hours in a day. Are you a short sleeper or just very efficient?

A: I start very early and I go very late. If you talk to people around the company you'd find that some people might get emails at four in the morning and they might also get emails at one in the morning… Whatever is needed I will do.

Q: How do you refresh yourself?

A: I love being with my family. My wife and I are empty nesters now, so we try to travel. My wife's much better than I am about being a tourist and she knows more about Australia than I do at the moment. I like sports. I'm learning about footy and rugby. I can't quite get taken yet by cricket. They tried in London when I was there, and some people are trying here, but I don't fit the right segment!