(FORTUNE Magazine) – Dick Grasso has hosted a lot of very important people in his office at the New York Stock Exchange--CEOs, Presidents, royalty, movie stars, you name it. Grasso doesn't exactly conceal this. Most of his visitors have left a memento or signed one of four large leather guest books, and his office is jammed with stuff. There is so much bric-a-brac, in fact, that it overflows into one of his colleagues' offices across the hall. There are signed pictures of Grasso with Bill Clinton, British Prime Minister Tony Blair, and Chinese President Jiang Zemin. There's the Superman painting Arnold Schwarzenegger gave him; a signed boxing glove from Muhammad Ali, Joe Frazier, George Foreman, and other former heavyweight champions; and scads of Sept. 11 memorabilia, such as the picture of the late fire chief Peter Ganci with a signed note of thanks from his wife.

It's a fascinating and intimidating tableau--what you might get if you combined the pageantry and tradition of the White House with the campiness of a flea market. You want to linger but feel as if you shouldn't. Grasso makes this decision easy for most guests. He keeps the place at around 90 degrees, so spending more than five minutes in it quickly makes one sweaty and somnolent. No one at the exchange seems to know how he tolerates this, and they dread meetings there. But you can tell Grasso revels in the quirkiness quotient it gives him. He occasionally shows up at staff meetings wearing his overcoat, and if you ask him why he likes his office so toasty, he elliptically responds that it's because of his bald pate--before adding that "it keeps meetings short."

Grasso certainly knows what it's like to sweat, though. At the height of Internet mania, the NYSE, the world's largest exchange, seemed doomed. Its chief competitor, the Nasdaq Stock Market, had been touting itself for a decade as the "stock market for the next 100 years," and back then it really seemed true. Its volume was bigger than the NYSE's and its top companies--Microsoft, Intel, Dell, Sun, Oracle, Cisco--seemed more important.

What's more, the Nasdaq seemed to be a heck of a lot more efficient. Trades were either completed by market makers sitting at banks of computer screens or, increasingly, by computerized systems like Island ECN and Archipelago. The NYSE, by contrast, looked like something Norman Rockwell would have painted. Jackets and ties were still required on the trading floor and in the members-only dining room. Stuffed animal heads lined the walls. Uniformed porters in cloakrooms took members' coats and shined their shoes. And while many parts of the exchange were computerized, stocks still traded more or less the same way they had since the specialist system was invented in 1871--at a trading post in a sea of paper on the floor.

Things were so bad that in one of the biggest bull markets in history, the price of an NYSE membership, or seat, was actually falling. The Big Board's largest member firms--Goldman Sachs, Morgan Stanley, and Merrill Lynch--were in near mutiny over how slowly the exchange was responding to the Internet. Like the rest of the big brokerage firms, they were spending millions to start alternative electronic markets, and suggested that the NYSE consider shuttering the floor and going electronic too. "The exchange simply looked like it wasn't going to be able to compete," says former SEC commissioner Laura Unger.

Visit the New York Stock Exchange today and it's hard to believe we're talking about the same place. It has the same trading floor, dining room, cloakrooms, and dress codes. But the idea of the Big Board's disappearing seems almost laughable now. Grasso gets a hero's welcome wherever he goes, seat prices are a hair shy of their highest ever, and some 85% of the FORTUNE 500 continue to list there. Nasdaq volume is still bigger but not by as much. And while Microsoft and Intel haven't left Nasdaq, other big tech companies like Network Associates and Sybase have. Even E*Trade is now a Big Board company. Two years ago it tried to position itself as everything the NYSE was not--remember those ads asking, "If your broker's so smart, how come he still has to work?" But now that E*Trade wants people to think of it as a bank, it lists on the NYSE. Says John Chen, Sybase's CEO: "Investors in the U.S. don't care where your stock trades, but we wanted to expand our business internationally, and investors abroad care a lot. They see Nasdaq as a technology-dominated marketplace and an incubator for young companies. They see the NYSE as a place where companies of quality list."

The big brokerage firms, meanwhile, have gone from being the biggest gripers about the exchange to being its biggest supporters. Goldman Sachs CEO Henry Paulson led a standing ovation for Grasso at the exchange's October directors' meeting. Goldman continues to invest in alternative markets, but in the past 18 months it also has spent nearly $7 billion to buy two NYSE specialist firms--Spear Leads & Kellogg and Benjamin Jacobson & Sons. "Back in 1999, I didn't think the NYSE was moving fast enough," Paulson says. "Today I couldn't be happier with the way they have responded."

Obviously a lot has changed in the two-plus years since the exchange was fighting for its survival. Khakis and polo shirts are out. Business suits and $250 custom-fitted shirts are in. That helps the exchange look less stuffy. Then there were the September attacks that shut down the exchange. For six days, Grasso and his team ran all the meetings, supervised the computer and phone-line testing, and acted as chief cheerleaders when the phone and electric companies, investors, brokerage firms, floor traders, and regulators worried that it couldn't be done in time. Grasso worked so hard that he spent two nights sleeping on his office couch. The result: At 9:30 A.M. on reopening day, Sept. 17, the exchange seemed like the most important place in the world. If the attacks were symbols of America's vulnerability, the NYSE's reopening was a symbol of its resolve.

Arguably the biggest factor in the exchange's comeback has been the stock markets themselves. It may seem ironic that the head of the NYSE got bailed out by a big bear market, but it's the truth. With CEOs focused on keeping their own business afloat, Grasso got some breathing room to work on his. And after a slow start, the exchange is now rolling out new products feverishly, courting and coddling its institutional investors as never before, and aggressively ramping up technology spending to speed up execution times, among other things. It now spends some $400 million a year on technology, up 25% since the late 1990s.

And the exchange is finally doing something critics thought it would never do: offering investors ways of trading stocks without a specialist at all, and letting investors see chunks of the specialist's once closely guarded order book. This is a big deal. The specialist, which is really a fancy name for a trader charged with being the buyer or seller of last resort in a stock, has been the soul of the exchange for 131 years, and Grasso has been one of its fiercest defenders. But he says you didn't have to be particularly observant to understand that the Internet was changing everything, and that without big reforms the NYSE would have been "competitively wounded." Longtime critics like Andrew Brooks, head equity trader at T. Rowe Price mutual funds, still say the exchange isn't moving fast enough, but he is more encouraged by what he's seen in the past two years than he's ever been. "For the first time they are actually listening to their customers instead of just their members," he says.

The impact is starting to be felt where it counts: on the floor. Specialists used to record trades on paper tickets, but they now use special software to fill them electronically. A trading platform with bandwidth of 50 gigabits per second, enough to handle 30 million simultaneous phone calls, allows them to process 6.5 trades a second, up from 1.6 trades a second three years ago. Floor brokers increasingly receive orders and record trades on wireless handheld computers. As a result, while volume is up 40% in the past 18 months, execution times are down 40%, to about 13 seconds. The most noticeable change? All that paper that used to make the exchange seem so antediluvian is rapidly disappearing. Since the start of 2001, paper use on the floor has fallen 30%, and it's expected to drop a similar amount this year.

At first blush, Grasso, 55, is the last guy anyone would expect to oversee such a revolution. He's an exchange lifer, having started in the then-moribund listings department in 1968 before being named executive vice president in 1982, president in 1988, and chairman in 1995. But the NYSE isn't like most corporations, where the CEO alone has the power to force a company to change course. It's a mutual, which means that it's run not by external independent shareholders but by its members. As a result, being CEO is more like being majority leader in Congress. You have to rule by consensus. And no previous chairman has been as well equipped to do that as Grasso. He's the only person from the exchange staff to become chairman. He has held every job in the place. He knows the exchange's history, arcane rules, and customs. And he knows everybody by name. That may not sound like much, but in an organization where the most powerful members work six floors below you, it's everything. Specialists and floor brokers control roughly 60% of the NYSE's seats, and Grasso is the only chairman in history they have really trusted. "I have a small firm, about 24 people. Small changes by the exchange could put me out of business, so if I'm going to go along I have to have a lot of confidence in the leaders," says floor broker Richard Rosenblatt, who's been at his job for 30 years. "I don't agree with everything Dick does, but I'll follow him."

Part of that trust stems from the fact that Grasso is the only chairman who's ever been like them. The floor itself now encompasses five rooms and 37,000 square feet. But it still feels like a locker room filled with smart, aggressive hustlers from New York City's outer boroughs. By contrast, the typical NYSE chairman has been a patrician, pedigreed ex-CEO. Grasso has no pedigree. He grew up in a working-class household in Jackson Heights, Queens. His father left the family when he was an infant, and he was raised by his mother and three sisters in a two-bedroom railroad flat. He didn't graduate from college. And he joined the exchange by default when he was 21. What he had really wanted to do was become a cop--until he failed the eye exam. It was a tough choice to make back then. His mother didn't approve. She and her sisters had lost most of their savings when the banks failed during Depression, and they looked upon Wall Street with suspicion. Grasso likes to tell a story about the day he became an exchange vice president. Instead of congratulating him, his mother said, "You could have been a sergeant."

But ultimately, the floor community trusts Grasso because he has pushed them to change the way they do business when they were afraid it wasn't in their best interest, and he has been right every time. Until two years ago, one of the biggest changes was putting the exchange on television. The floor community had a long history of trading stocks without the rest of the world watching--starting in the 1920s, specialists had curtains pulled across the windows. In the mid-1990s, Grasso convinced everyone that by making the exchange better known among individual investors, specialists and brokers would reap a huge windfall from the explosion in volume.

Anyone with a TV knows what happened next: The exchange floor became the biggest television studio on the planet, with 22 media outlets broadcasting from its floor on a regular basis. And Grasso has turned himself into the exchange's showman-in-chief. Opening and closing bells are photogenic events. Within days of each other last month, Olympic figure-skating champion Sarah Hughes and Yamila Diaz-Rahi, this year's Sports Illustrated swimsuit-issue cover girl, were there. In February, Mr. Potato Head celebrated his 50th anniversary. Today there isn't a big-time celebrity, politician, or foreign dignitary who doesn't try to ring the bell when he or she is in town. It's in such demand that some companies book a date three years in advance. Grasso sums up his approach to running the exchange like this: "In case you haven't gotten it, I don't have the face, I don't have the height [he's about 5-foot-6], I don't have the blood. I don't have any of the right things, okay? So I'd better at least want to win."

To understand the current set of reforms, you have to go back to 1999. With big brokerage firms threatening to defect and the Nasdaq growing ever more powerful, the NYSE's specialists and floor brokers felt backed into a corner. Grasso's solution? Change exchange rules to let the companies that list on the exchange pick their own specialists. This may sound small, but, says Michael LaBranche, CEO of LaBranche & Co., the floor's largest specialist firm, "it was a watershed." Before then a committee at the exchange had assigned a specialist to a company. The specialists liked it because it they were guaranteed a certain number of stocks. But companies hated it. Grasso says, "Here they had spent years in business priding themselves on making all the right choices--the right product, the right market, the right employees, the right lawyers, investment bankers, you name it--and then they get to the altar of the NYSE and we say, We'll choose the person who trades your stock? To them and to us it flew in the face of competitive capitalism." He says it was a big reason the exchange was having trouble attracting new listings, particularly in high tech. Grasso's pitch was straightforward: The two most important elements for a specialist's income growth are increased trading volume and new listings. Here was a way to accomplish both for all but the weakest of them.

In addition to being an important signal to companies that the exchange was getting serious about reform, it also turned out to be a political masterstroke. Because specialists no longer were guaranteed listings but had to compete for them, their economic interests suddenly became much more closely aligned with the exchange's, so they became easier to deal with. Before, it was up to the exchange management to go after new listings. Now specialists, hoping to get an edge, were joining that hunt. More significant, the change forced them to consolidate, with the stronger players like LaBranche gobbling up the weaker players. Now when Grasso wants to make a change, he has to convince only eight specialist firms, compared with 35 four years ago.

Grasso has taken advantage of this newfound flexibility. For example, when critics groused that specialists were the only ones who knew the true supply and demand in a stock and that this was a license to make money at the expense of everyone else, the exchange earlier this year offered Open Book, a product that will give anyone who pays for it real-time access to the specialists' buy and sell orders. (Peeking ain't cheap. The price tag: $600 a year per person.) More changes are on the way. In the fall the exchange will start offering two kinds of stock quotes to investors: the standard quote it offers now, plus a quote telling institutional investors what the price to buy or sell a giant block of stock would be. Institutional investors have been clamoring for this since stocks began trading in decimals rather than sixteenths or eighths, at the end of January 2001. Their point: Now that there are 100 different prices between $20 and $21 instead of 16 or eight, there isn't as much stock available to buy or sell at each price. That makes it harder to judge what the true demand for a 100,000 share order is anymore.

And in a year or two, the NYSE plans to augment Open Book by offering traders ways to analyze all that information, also in real time. Says Bob Britz, the exchange's new president, "I know every order in AOL by size, by type, by expiration date. Stuff that's on the specialist's books and stuff that's not. No one knows any of that. What you know are the bids and offers that result from that. I know what the inputs are." He's not about to divulge who's sending the orders, of course. But he does hope the information will generate enough cash so that the exchange can lower annual listing fees--which for large companies are $500,000, vs. $60,000 for the Nasdaq. The high cost of listings is one of the biggest complaints from Nasdaq firms pondering a switch.

Is all this change enough? Grasso's critics complain that his reforms are still too cautious. "He's taking baby steps," says John Wheeler, head equities trader at American Century mutual funds. "Most of the things he's rolled out, the institutional community has been demanding for years." Others gripe that Grasso hasn't done enough to police specialists and floor brokers. Most of the time the primary function of the specialist, as the trader of last resort, is not to participate in trading but simply to match buyers and sellers at the best price. But more than anyone else on the floor, the specialist knows what the supply-and-demand pressure in his stock is, so the temptation to use that information to "trade in front of" those buyers and sellers, which is illegal, can be great--and the line between that and his responsibility to keep the market moving can be fuzzy. It's why companies like Liquidnet, which would allow institutional investors to find one another away from the exchange, are seeing rapid increases in volume this year. They haven't made a dent in the exchange's market share yet, but one day they will, Wheeler predicts.

And then there is the more fundamental question: Whether you are a fan or a critic of the Big Board's specialists, you have to wonder how long the exchange can continue to process more and more volume with a 131-year-old system. An interesting test will come in the next year when Nasdaq roles out a new trading system called Super Montage, which is basically a large order-matching system, or ECN.

Grasso's answer is to continue automating until specialists handle only the biggest and most complicated trades and the rest don't get touched by human hands at all--"high tech and high touch under the same roof," he likes to say. Specialists are still needed, Grasso argues, because computerized trading fueled by the 24-hour news cycle allows investors to react instantaneously. "That makes the markets more sensitive and more volatile," he says, and more than ever that means someone needs to be able to step in and calm things down. Investors don't like it when stocks jump around, because they have a harder time getting the price they want. And Grasso believes that electronic exchanges, by their very nature, can't dampen this volatility as well.

Critics like Jay Peake still don't buy it. "There is no question the exchange is in a battle for its life," says Peake, a professor of finance at the University of Northern Colorado. "As computers make trading more and more commoditized, the exchange will find that its costs are simply too high to be competitive." Right now, however, even Peak acknowledges that it's hard to argue with Grasso's success. "I wish he hadn't been successful, but that's the way it goes." Let's see what happens when the bull market returns.

FEEDBACK: fvogelstein@fortunemail.com