FORTUNE — To say that Priceline CEO Jeffery Boyd’s persona is different from that of the Negotiator — the boisterous, charmingly obnoxious Priceline pitchman portrayed so delightfully by William Shatner — is an epic understatement.
Boyd may try to dress like an Internet entrepreneur — he greets me tieless and sockless, wearing docksiders, a button-down shirt, and linen slacks — but the 56-year-old still looks and sounds a lot like the buttoned-up former Sullivan & Cromwell corporate lawyer he once was. When I met Boyd at Priceline’s headquarters in Norwalk, Conn., in mid-August, Priceline’s stock was reeling. Boyd had just warned that third-quarter travel bookings were growing more modestly in Europe because of economic weakness, and Wall Street panicked, sending the stock down 17%. “Deterioration or Deceleration?” blared the title of an analyst report on Priceline (PCLN), the world’s leading standalone online travel agency, with $4.8 billion in annual revenue, vs. Expedia’s (EXPE) $3.7 billion.
The blustery Shatner (and certainly many of Boyd’s CEO peers) might have responded by denouncing Wall Street’s overreaction or by hyping all the reasons any dip in Priceline’s prodigious growth must be viewed as anomalous. Boyd? He shrugs off the wipeout of $6 billion in market capitalization as if it were a paper jam in the second-floor photocopier. “Some managements tout their stocks and really try to encourage people to invest. We don’t do that,” says Boyd. “Our job is to manage the business, not the stock. The business is doing great and gaining market share, but we’ve also been very candid that growth rates do decelerate over time for any company now this big.”
Whether investors view such candor as scary or refreshing probably depends on how long they’ve owned the stock. Among mutual funds, 72% of Priceline’s owners are growth funds, some of which bail at the first whiff of bad news. But investors who remember Priceline’s dysfunction under founder Jay Walker and have held on to the stock during large chunks of the Boyd era are more appreciative. “There’s not a lot of the hype that you sometimes see coming out of Silicon Valley,” Barclays analyst Anthony DiClemente says of Boyd’s tenure. Indeed, Priceline lies far from the high-tech hub of Silicon Valley, and Boyd likes it that way. Its humdrum offices lack any whiff of Internet chic (“We prefer to spend money on things that grow the business,” he says); one advantage to its Connecticut location, he adds, is fewer bidding wars for programmers and web designers than in the opportunity-rich Bay Area. “There are a lot of CEOs who are very good at the talk, at the bluster, at the marketing message,” adds Mike Lippert, portfolio manager of the Baron Opportunity Fund (BIOPX). “That’s not Jeff Boyd. He’s kind of a bland guy who tells it like it is and lets the results speak for themselves.”
Those results have been superb. Since becoming CEO in 2002, Boyd has turned this former poster child of the dotcom bust into one of the great e-commerce success stories — taking it from a loss of $19 million in 2002 to $1.1 billion in profit in 2011. The stock has gone from $8 to $604 a share over the same time. Even at its current size — with $4.8 billion in revenue and a market value of $29 billion — Priceline remains one of the fastest-growing companies in the U.S., checking in at No. 14 on Fortune’s Fastest-Growing Companies list. The question now is whether weaker-than-expected second-quarter earnings and that cautious guidance for the third represent a mere lull or the beginning of the end to Priceline’s amazing growth story. Boyd remains optimistic, but it certainly doesn’t sound as if he expects the company to be sitting near the top of America’s fastest growers for much longer. “We’ve been telling investors for years that when a business gets to be the size of our business, it’s very, very hard mathematically to maintain high growth rates,” he says. Even so, Priceline trades at 20 times projected 2012 earnings, an attractive multiple for a company that analysts expect will grow its earnings 29% this year.
Boyd came to Priceline as general counsel in 2000 on what has to be one of the more random career paths for a future CEO. From 1995 to 2000 he had been the general counsel for Oxford Health Plans, which, coincidentally, was located in the same Norwalk building as Priceline’s headquarters. (“Part of it was geography,” he admits.) Lured by the prospect of dotcom riches, several Oxford executives had already jumped ship to Priceline, and among them was the head of HR — who eventually recruited Boyd. “Priceline was engaged in a lot of deal activity at that time, trying to build a bunch of international joint ventures,” says Boyd. “For a deal lawyer like myself, what could be more fun than that?”
At the time, Priceline was a true dotcom darling, one with a well-known “Name your own price” gimmick and a founder, Walker, who in hindsight was better at raising money from investors than making money for them. Before Priceline ever turned a profit in the travel sphere, it had already expanded into “Name your own price” gas fill-ups, groceries, insurance, mortgages, long-distance phone service, and new-car sales. The company lost $1.1 billion in 1999, and when the dotcom bubble burst the following year, Priceline stock cratered from $974 to $7 a share. As Boyd says, “There was a credibility issue.” (Walker could not be reached for comment, but a Priceline spokesperson says he left the board in 2000 and has no involvement in the company.)
By 2002, when Boyd took over as CEO, the company seemed destined for the same sad fate as Webvan, Pets.com, and all the other early dotcom busts most investors would prefer to forget. But the one thing Priceline had going for it that those others did not was a popular, recognizable brand. While Priceline’s “Name your own price” service certainly wasn’t for everyone — yes, you can fly from Boston to Miami for $100, but only if you don’t mind a six-hour layover in Dallas — Shatner’s Negotiator character, who shows up out of the blue to help consumers save money, immediately resonated with a public frustrated by confusing airfares and amused by the former Star Trek star’s self-parody. “The problem with a lot of advertising is people remember the ad but don’t remember which brand it is for,” explains Boyd. “People very quickly associated the Priceline brand with William Shatner, and the benefit for us was instant name recognition.”
Boyd’s turnaround plan for Priceline centered on shuttering the nontravel businesses, and then, even more controversially, focusing Priceline’s resources on hotel bookings instead of “Name your own price” airfares. The problem with airfares was twofold: The Internet had made ticket pricing more transparent, and then the devastating impact of 9/11 forced the airlines to downsize. More transparent pricing plus fewer empty seats meant fewer opportunities for a bargain travel business built on last-minute ticket sales. Back then, 80% of Priceline’s business was “Name your own price” airline tickets. “We were really struggling to maintain pricing and inventory in that environment,” says Boyd.
Even absent the airline industry issues, Boyd had doubts about the broader appeal of “Name your own price” airfares. Consumers had little control over the time of their flights or the length of any layovers. While a college student might be willing to accept such uncertainty in exchange for a cheaper fare, vacationers or business travelers were much less apt to do so.
Another controversial change: Boyd decided to offer traditional pricing along with “Name your own price.” While some within the company thought that would confuse consumers and damage the Priceline brand, Boyd saw mostly upside. “We felt very strongly that it would only help build a better product because it makes ‘Name your own price’ that much easier to use,” he says. “Our advertising used to say, ‘Shop around at other sites and then come back to Priceline.’ What company in the United States sends the consumer to their competitor?”
Priceline earned its first profit in 2003, but the company’s true turning points occurred in 2004 and 2005, when Boyd acquired two European hotel reservation sites — the U.K.’s Active Hotels and Amsterdam-based Booking.com. Priceline’s earnings growth and stock market success since then have been attributable largely to those two acquisitions — Booking.com in particular. “It would be tough to argue that there’s been a better acquisition in Internet history,” says Thomas White, an analyst at Macquarie Securities. “It’s why the stock has been such a home run,” says White. Both he and Barclays’ DiClemente believe that many investors don’t realize that 60% of Priceline’s revenues are now coming from overseas. “One of the first things I tell [new] investors is to put William Shatner out of your mind,” says White. (While U.S. users can also use Booking.com, Boyd doesn’t worry too much about cannibalization.)
Boyd had good reason to target Europe. Europeans typically have twice as many vacation days as Americans, and unlike us, they tend to take all of them. Moreover, the growth of discount airlines in Europe such as EasyJet and Ryanair have increased the popularity of “city breaks” — the European equivalent of a weekend getaway.
Best of all, the European market for online travel services still has much room to grow. Compared with the U.S., a much smaller percentage of travelers book hotels online, a byproduct of the fragmented nature of the European hotel industry. There are far fewer big hotel chains, which means travelers are more likely to be considering stays at independently owned hotels — which rarely have their own websites. Unless travelers are familiar with the city they are visiting, it’s hard for them to differentiate the overpriced fleabags from the gems worth every euro. Priceline typically collects a 15% commission on every room reserved at Booking.com; in return, the hotels get access to more potential customers. “If you own a great hotel in Prague, you’re probably going to have a very small marketing budget,” says Darren Huston, a former Microsoft (MSFT) and Starbucks (SBUX) executive who became Booking.com’s CEO in September 2011. “You might get to a certain level of occupancy via word of mouth, but you would have difficulty marketing to Russians or Brazilians or people from the Middle East because you don’t have a brand name.” Booking.com helps level the playing field.
But the European focus is also partially responsible for the recent earnings miss, which Boyd made no attempt to sugarcoat during an Aug. 7 earnings call. “We’re assuming fairly significant deceleration [for] growth rates from here on,” he said, citing concern about the economy and “our worry that conditions will worsen, particularly in Europe.”
Can Priceline still be a growth company if Europe doesn’t snap out of its malaise? Probably yes. Priceline is still expecting 15% to 25% earnings growth in the third quarter, and the company has an increasing presence in Asia via its Agoda brand as well as a new partnership between Booking.com and Ctrip, China’s top online travel site. Another potential growth business is rental cars, boosted by the 2010 acquisition of global car-rental site TravelJigsaw.
Not all the recent news out of Priceline has been so weighty. Shatner’s Negotiator character has been MIA from Priceline’s TV commercials since January, when he was presumably killed after plunging off a bridge in a doomed tour bus. But last month the Negotiator was resurrected in a new TV spot in which he realizes that someone has to tell the world that Priceline now has “even easier, faster ways to save you money on hotels, flights, and cars.”
Explaining Shatner’s hiatus, Boyd says it’s important that consumers understand “the full spectrum of products available” at Priceline. In June, for instance, Priceline launched a new “opaque” product called Express Deals, which basically mimics rival Hotwire and allows consumers to get published discounts on hotels — but you don’t know the identity of the hotel until after you’ve paid. Since “Name your own price” was so synonymous with Shatner, Boyd felt he needed a fresh message for Express Deals. The campaign with Shatner going over the bridge, Boyd explains, “was a way to demonstrate that there was more going on [at] Priceline.”
But the people wanted their Shatner. According to the company, 94% of Priceline customers surveyed wanted the Negotiator to return, and in a bit of either shrewd or serendipitous timing, Shatner’s resurrection became the Priceline news of the day, displacing the disappointing second-quarter earnings. The people got their way, but the hubbub made clear the disconnect between how Priceline is perceived by casual investors and the true international nature of its business.
Boyd doesn’t seem terribly worried about this. He’s more focused on growth opportunities in Asia and South America. In the new Shatner ads, the Negotiator is miraculously found alive by a Priceline agent who tries to convince him that his mission isn’t over. Jeffery Boyd needs no such convincing.
This story is from the September 24, 2012 issue of Fortune.