(FORTUNE Magazine) - The company is likened by some to the Roman Empire, by others to that misunderstood giant of sci-fi films, Godzilla. Getting to see its leader, though, feels more like Mission: Impossible.

The sounds of traffic on Manhattan's Park Avenue disappear as you enter the headquarters of the largest, most formidable financial institution the world has ever known. More than a dozen security guards man the lobby, and once your identity has been ascertained and confirmed--and it matches a guest-admission list on the computer system--you are escorted by a single envoy into a special elevator. The machine whisks you up just one floor, the guard still by your side. A new gatekeeper takes over, and you are led through a maze of soft rugs and wood-paneled walls.

And then, suddenly, you're there, sitting across from Charles O. Prince III, the 56-year-old chief executive officer of Citigroup (Research). His 6-foot-4 linebacker-esque frame is economically packed into a club chair in his palatial yet understated office. His desk, at the other end of the room, is pristine. His computer glows, but too far away to reveal any secrets. He has a reputation for being folksy at some times and bristly at others, and is generally averse to introspection. His words on this midwinter morning have a scripted air. Yet every now and then, confidences emerge.

"I'll try things to see if they work," he says of his initiatives at Citi, as if he's experimenting with a recipe instead of a 300,000-person company with operations in 100 countries, $100 billion in shareholder equity, and more than $1 trillion in custodial accounts. Citigroup's former general counsel--a lawyer with only limited operational experience--Prince describes a predilection for micromanaging that doesn't quite fit his current job description. He talks about reading biographies (on Ronald Reagan and F.D.R.) to glean leadership lessons: "You pick up things you can apply," he says. He is essentially admitting that he is not the consummate CEO, at least not yet, and in some ways the sentiment is endearing, even charming. "I'm a doer," says Prince, who is known as "Chuck." But it is also a bit disconcerting, this undertone of inexperience, given that each of his company's four divisions is itself the size of a FORTUNE 1,000 enterprise. (Citigroup was No. 8 on last year's list.) Perhaps his self-deprecation is calculated, that he is just being coy.

Or perhaps not. Right next to Prince's office is the lair of Robert Rubin, 67, the former Treasury Secretary and Wall Street luminary who is a Citigroup director and chairman of the executive committee. Rubin has worked with--and counseled--some of the greatest business leaders of the modern era. So his assessment of Prince, while gently put, is biting in its implication: "He has the potential to be a great CEO," Rubin says during a separate interview. Rubin talks about how he encouraged Prince to hire as chief administrative officer Lewis Kaden, 63, a lawyer from Davis Polk and a longtime consigliere to business titans, to add more depth to the Citi management team. Kaden, who started last fall, has his office on the other side of Prince's, giving the CEO another gray eminence near at hand to turn to. "It was a good plan to get Lew in," Rubin says. "It's working well."

Across Manhattan, in a different corporate world headquarters, another Prince advisor echoes this on-his-way-but-not-there-yet theme. "He probably didn't have enough line experience [when he became CEO]," says Citigroup board member Richard Parsons, the chairman and chief executive of Time Warner (Research) (which owns this magazine), from his 11th-floor perch in the Time Warner Center on Columbus Circle. "He's turning out to be a better leader than we hoped. Still, you can't anticipate the experience of being CEO."

It seems almost unanimous--among employees, former employees, investors, analysts--that 2½ years into his job, Chuck Prince is still feeling his way. That might be unremarkable except for one thing: While learning on the job, Prince has taken it upon himself to stage one of the most difficult turnabouts ever attempted on Wall Street. Citigroup was built, metaphorically brick by brick, by the colorful and loquacious Sandy Weill, Prince's mentor and predecessor. It was Weill who masterminded the unlikely string of acquisitions that created the Citi behemoth, who lobbied regulators and politicians to lift laws that would have prevented it, who wowed investors into cheering its stock and motivated managers and rank-and-file workers with his distinctive, charismatic operational style. Prince, as a longtime Weill acolyte, benefited from all of that. Yet now he has committed himself and Citi to completely tearing up Weill's management system and philosophy. Organizational structure has been revamped, priorities--in particular, the imperative to meet each quarter's earnings estimates and worry about the long term later--have been rearranged, and heads have rolled.

Why? In part, Prince has been prompted by a string of Citi scandals to put ethics on an equal footing with profitability. (He personally sermonized to 45,000 employees in a series of town hall meetings around the world.) But he's also responding to a fiscal reality: The growth-by-acquisition route that Weill plied so superbly has ceased to be effective--and with Citi so enormous, as Prince has quipped, "the only way we could do a transformational acquisition would be to buy Canada." Instead, Prince sees Citi's future as dependent on organic growth, which in turn will require a more efficient, centralized, and systematized corporate culture than the one Weill bequeathed to him. If that means breaking a few eggs, chef Chuck seems ready and eager to get cracking. ("I'm impatient," he confesses. "I want things done yesterday.")

Prince, who has little of Weill's populist appeal and none of his hard-earned Wall Street cred, is engendering enormous skepticism both inside the company and out. In the past year a slew of high-ranking, experienced managers at the firm have exited. A swelling chorus is questioning whether the bank even needs this complete reengineering. Prudential Securities analyst Mike Mayo put out a positive note about Citi's prospects on Feb. 16 but cited "ongoing concerns about its management." Says Merrill Lynch analyst Guy Moszkowski: "Sandy [Weill] was a rock star. Investors were in awe of him because he made a lot of people rich." In contrast, when Prince's name comes up, critics are likely to utter the word "lawyer" in a pejorative tone. (That is no news to Prince, who jokes that they usually say he's "just a lawyer.") As one industry insider puts it: "It's like they took the lawyer for an NFL team and made him the quarterback overnight."

The pressure to perform--and soon--is almost palpable. During his tenure, Prince has overseen a 40% hike in the dividend and in 2005 alone plowed almost $13 billion into share buybacks. Yet Citi's stock has languished, returning just 10.8%, including dividends, since Prince took the helm, vs. 34% for the S&P 500 and 33% for the S&P 500 financials. When Citi announced its fourth-quarter earnings on Jan. 20, Wall Street was disappointed--for the third consecutive quarter--and the stock dropped almost 5%. Industry publication American Banker chided Prince and CFO Sallie Krawcheck for repeatedly blaming a "challenging" external environment during their quarterly conference call, counting up 11 uses of the word during the 80-minute presentation.

Shareholders aren't calling for Prince's head. He is, after all, dealing with less than hospitable economic conditions, including a flattening yield curve and a shriveling mortgage market. Citi's board remains supportive: When Weill steps down as chairman this spring, Prince is the odds-on favorite to add that title. But there's no question that Wall Street is getting antsy. Says Citi's biggest investor, Prince Alwaleed bin Talal bin Abdul Aziz al Saud, who owns close to $11 billion of stock: "It's all wonderful and lovely that Chuck Prince has cleaned up Citigroup. But we now need him to execute growth and boost the stock price."

It's Dec. 16, and more than 100 analysts and reporters have gathered for Investor Day in the 12th-floor auditorium at Citi's Park Avenue headquarters. The slickly staged presentation begins with a booming, big-screen-video melange of Citi's television ads from all over the world. The commercials, in different languages, highlight the company's deep global reach and induce a few chuckles as well as muted oohs and aahs from the crowd. Then the lights come up, and Prince takes the stage, exuding confidence and energy: "I know where we are taking this company! I know how we are going to get there! My job today is to make sure that you know it as well!" He throws an air punch--pow!--in Howard Dean-esque fashion.

It's an unexpected, and somewhat forced, display of theater from a man whom Bob Rubin describes as "the thinking person's CEO, vs. a flamboyant, charismatic CEO." But if Wall Street's lukewarm reception over the past few years has taught Prince anything, it's that he's got to get a little more of Sandy Weill's flash into his public persona. "He should be out there selling the Citi story!" exclaims Alwaleed. "If he's publicity-shy, then it's my job as a shareholder to have him change that habit."

Weill certainly didn't need to be coached. An inspiring leader to many, he built Citi from the bit parts of a low-rent consumer-finance outfit called Commercial Credit. Among those bit pieces was a young lawyer named Prince, who latched on to Weill and played a helping role as he acquired a string of companies: Primerica, Shearson, Travelers, Salomon Brothers, and finally Citicorp. Prince was the jack-of-all-trades who planned Weill's annual birthday bashes (and often emceed them), wrote many of Weill's speeches (as well as a skit in which Weill appeared onstage dressed as Moses, ready to deliver his employees to the promised land), and signed off on most documents before Weill got to see them. He was so devoted to Weill that Prince's own mother said to the Los Angeles Times shortly after he was named CEO, "I always ask [Chuck]: 'What are you doing next time for Sandy?' "

Prince became Weill's fixer, working on everything from the Argentine peso crisis to Citi's Enron and WorldCom exposure. In 2001 he ascended to the title of chief operating officer, and the next year was moved over to run Citi's investment banking unit. He negotiated directly with New York State attorney general Eliot Spitzer over alleged conflicts of interest. (Prince, ironically, is referred to as "C.O.P.," his initials, by some Citigroupers.) When Weill named a successor as CEO in the summer of 2003, amid fallout over his own questionable behavior, Prince was the stunning choice.

Citi's stock fell nearly 3% on the news, an inauspicious start. Weill stood by his protege, proclaiming when Prince officially took the reins in October 2003 that he had "no doubts he was the right man for the job." Prince certainly seemed unlikely to undermine Weill's legacy. "Sandy assumed," says a former executive, echoing the sentiments of many Citi stalwarts, "that as CEO, Chuck would more or less go along with Weill's decisions." (Weill remained chairman.)

But during his first few months Prince started "to poke under couches to see what was there," according to a Citi board member who asked not to be identified. Prince, this person says, was astonished by what he found. In some divisions, tools like accounting software were antiquated or nonexistent. Conduct codes, if they existed, were often loosely worded. Most Citi managers were so focused on quarterly earnings and revenue targets that divisions competed with one another, often in a bloodthirsty manner. "They would eat each other for lunch if they could," says a former Citi division head. Prince became increasingly troubled that there was no unified culture at the bank, no shared history. "It was kind of like Yugoslavia," says board member Parsons.

To Prince, the lack of internal controls and systems was unacceptable. That became all too clear when Citi's private banking operation in Japan was charged by regulators with taking part in money laundering and selling risky products to customers, among other things. The private bank was forced to shutter operations there in the fall of 2004. Other troubles followed: in Europe, a bond-trading investigation surrounding a scheme dubbed "Dr. Evil"; a class-action suit in the U.S. filed by shareholders of Global Crossing; accusations in Italy of helping Parmalat create a complex financial structure called buconero--"black hole" in English --that allegedly allowed the dairy company to hide debt. (Citi denies the Parmalat charges and, despite settling, the Global Crossing suit allegations.) Prince started bulking up compliance, reportedly doubling the staff.

Several months into his tenure as CEO, Prince took an important symbolic step: He moved his office from next door to Weill's on Citigroup's third floor down to the second floor. "He wanted to physically separate himself," says a former executive. Prince also began talking up the idea of a "new Citi," repeating mantras like "My job is not to run a museum" and calling Citi a "battleship" that needed "to be turned around." Parsons says it was a terrifically tough period for Weill. "We would be in board meetings, and Chuck, especially in the beginning, came on a bit strong. He'd say those things, and Sandy would just stare at the ground." Prince had always followed Weill's counsel in the past, says Parsons, but now the tables had turned: Whenever Weill tried to give advice, Prince would "maybe take three out of the five suggestions."

At the same time, Prince sought out Weill's former co-CEO, John Reed--whom Weill had famously pushed out in February 2000--for advice. To the shock of some Citi execs, Prince took to quoting Reed-isms publicly, at one point telling the Harvard Business School newspaper, "John Reed used to say that the most important part of a racecar is the brakes, and that you can't drive fast unless you have the ability to stop."

Prince and Weill communicated mostly through staffers. "Sandy was grumpy for a while. Let's face it, he wasn't The Man anymore," says Parsons. (Weill was not made available for interviews.) Prince and Weill have since reconciled, according to Parsons, with Joan Weill, Sandy's wife, bringing the two together. Prince says he's remained close with Weill, continuing "to have standing lunches on Mondays."

Meeting him now, it's hard to believe that Prince was once known as "the resident funny guy at Citi," according to a former executive, who also recalls Prince's keeping a bowl of candy in his office to lure visitors. A child of sunny California--growing up just a few miles from Disneyland--Prince played the trumpet as a teenager and had dreams of becoming a professional musician. He also had a studious side. Prince (whose mother was a homemaker, and father, a construction worker who later became a union boss) eventually piled up academic accolades: bachelor's and law degrees from the University of Southern California, and two master's degrees from Georgetown.

As the CEO, say several former Citi execs, Prince underwent a personality change. "He became much more serious," as one puts it, "almost imperial." Always prone to the I'm-a-workaholic-and-proud-of-it badge, Prince became even more so and pushed those around him to follow suit. "Chuck is a stickler when it comes to deadlines," says CFO Krawcheck. "He gives you a task to do, sometimes a monumental one, and asks for it about two days earlier than you'd expect."

Prince also became a hostile target for Weill fans who disagreed that Citi's operations needed radical fixing. "Nobody thinks of Prince as a visionary or a great leader," says one such critic, still a top Citi manager. Early on, Prince made bold statements that struck some of the naysayers (none of whom was willing to speak for attribution) as naively overreaching. A former senior executive says that at one meeting, Prince announced a goal for Citi of $50 billion a year in profit within five years. "We were aghast," says this person, who notes that earnings at that point were running at about $18 billion. "This was just laughable." (Prince says it was merely an exercise to get people to think on a multi-year basis.)

To clean house after the regulatory scandals, in the fall of 2004, Prince fired some heavy-hitting Weill loyalists: Thomas Jones, who ran asset management; Deryck Maughan, the former Salomon CEO who headed international operations; and Peter Scaturro, CEO of the private banking group. At one point Weill had considered both Jones and Maughan for the CEO job. Other former Citi execs say the fired men were not just scapegoats for the Japan problems; "Chuck wanted people he was threatened by out of Citi, and he's achieved that," as one puts it. Responds Prince: "A good manager isn't threatened."

In the past year Prince's managerial style and decisions have prompted the voluntary exit of more senior execs with several years of operational experience at Citi. Most notable were Marge Magner, who had been with Weill from Commercial Credit days and ran consumer banking, and Robert Willumstad, Citi's president and chief operating officer. When Prince was installed as CEO, Willumstad was reportedly viewed by Weill and the board as an essential part of the deal, to provide operational experience--he was paid a salary and bonus identical to Prince's. (Since walking away, Willumstad has not taken another job but has been recruited to join the board of insurer AIG.)

The turnover is not viewed everywhere as a problem. "The Sandy crew underperformed," says Richard Bove, an analyst at Punk Ziegel. "Chuck absolutely needed his own new team." Prince has brought fresh blood into the top echelon of Citi, turning to the 41-year-old Krawcheck as a key player, tapping former CFO Todd Thomson, 45, to run Smith Barney, and splitting consumer banking between Ajay Banga, 46, and Steve Freiberg, 48. Some question whether this team has the experience to manage such a huge and complicated global enterprise. Even board member Parsons stresses, "The most important thing for Chuck is to get his team functioning at the highest level. He needs to get them to be super-effective, and fast." Prince says he has a great team "with new ideas, new thinking."

Not one to tread softly, Prince has radically changed the way decisions at Citi are made. Earlier this year he bulked up the management committee to nearly 100 members to give greater exposure to more executives. At the same time, he's created a smaller 14-member business-heads committee. There's also a 34-member operating committee. Some bridle at a system that requires more meetings. "That's what he thinks of as streamlining," says a former top executive. "Things get kicked around so much in these committees that many decisions are being made more slowly than ever." One former exec calls it the "catch-and-release decision-making process: I thought we made that decision already, but here it is again, swimming around, like a fish." (Says Prince: "This is such a huge company, you have to have a certain amount of bureaucracy.")

To combat complaints--and gauge their universality--Prince has launched a morale indicator called the Voice of the Employee and an initiative called the Wax Removal Program to fight excessive bureaucracy, including a website where staffers can vent about unnecessary rules. One top Citi manager says he went "to complain on Chuck's Wax Removal site" and found himself exasperated by the bureaucracy of the site itself: "There were so many questions, I just gave up." But Prince is unrepentant and adamant that Citi needs to develop a more cohesive corporate culture; he's even taken to handing out books about Citi's history (example: The Banker's Life, by former Citibank chairman George S. Moore) to his top managers. "We can't grow as fast as we want to grow," Prince declared at an investor conference last summer, "if we don't have a culture, if we don't have the controls, and if we don't have a set of internal values that serve as a foundation for guiding our business practices."

Ultimately, of course, Prince knows that his success lies in the numbers, not the number of new programs. Earnings in 2005 clocked in at almost $25 billion, a record for the company, though that was boosted by one-time events, such as $4.2 billion in gains from the sale of assets. (Prince got Citi out of the asset-management business last year, trading it to Legg Mason in exchange for that firm's 1,200-strong brokerage network; he also got out of the insurance business, selling off Travelers Life & Annuity.) Some of Citi's operations--most notably underwriting and M&A--are booming. But the institution that invented the ATM and the certificate of deposit also finds its U.S. consumer banking division lagging far behind Bank of America and Wells Fargo in number of domestic branches, with about 900, vs. 6,000 and 3,200, respectively. Prince plans to add as many as 100 U.S. branches this year, and is looking to make what he calls "string of pearls" purchases--businesses that mesh with its existing infrastructure. Most of Citi's future growth, he says, will probably come from overseas, where, with the exception of Mexico, it has single-digit market share yet widespread brand awareness and an existing toehold. Citi, he notes, is the only U.S. bank that already has a global presence it can build on. In January a Citi-led consortium purchased an 85% stake in China's Guangdong Development Bank Co., making it the first foreign firm with controlling interest in a Chinese lender.

His growth plans won't blossom overnight, and he acknowledges that, lamenting, "Investors want to know what you'll do in the next 90 days to make the stock go up." He's got to keep those shareholders at bay so that his longer-term efforts have a chance to hit the bottom line. Analyst John McDonald of Banc of America Securities gives Prince "points for making decisions that depress current results for the benefit of long-term growth potential." But McDonald also downgraded the stock on Jan. 4, from buy to neutral, primarily citing Citi's organic growth challenges.

Prince and his people assert that much of his cultural and managerial framework is now in place. Others say it's a monumental work in progress. Observes Harvard Business School associate professor Rakesh Khurana: "The culture can't change overnight. Citi is deeply rooted in past decisions and strongly held belief systems."

Prince may not be the natural leader his predecessor was, but given Citi's challenges--and the imperative for stricter controls because of a string of scandals--the board sees him as the right chief right now. Parsons compares Prince's CEO-dom to the rule of Augustus Caesar. "After Julius Caesar," Parsons notes, "he was the one who had to come in to put in the infrastructure so the place would be around for the next hundred years." Julius Caesar, you may recall, was assassinated by conspirators led by Brutus. Augustus Caesar, in contrast, lived to the ripe old age of 76. Prince's plan is surely to follow in those footsteps.

FEEDBACK mvickers@fortunemail.com

REPORTER ASSOCIATE Doris Burke contributed to this article.