Credit: Photograph by Mark Seliger

The first thing Anthony Bourdain does upon arriving in a city he's never been to — a small category that's shrinking quickly — is to drop his bags and head straight for the central market. Even in a globalized 21st-century metropolis, where Starbucks and foodie blogs have sapped away most mystery, the market, Bourdain believes, can still be counted on for authenticity. "You see what's for sale, you see what's in season, you see the fundamental color palette of a cuisine," he says. "You really get a sense of what a culture loves most dear."

On the other hand, the first thing Bourdain does upon arriving in a city he knows well — like, say, on his fourth trip to Kuala Lumpur — is go straight to his hotel and promptly take a nap. Which is why, on this humid Malaysian summer evening, six hours after he touched down, and 30 hours after he took off from New York, the 59-year-old Bourdain strides into the lobby of the soaring Grand Hyatt Hotel, refreshed and blinking sleep from his eyes. "Ready for dinner?"

His van is due at 6:30. It's currently 6:19. Bourdain is a man who neither tolerates nor indulges in lateness. He's wearing his standard traveling uniform — rumpled oxford shirt open to the third button, worn-in jeans, tan desert boots, silver Rolex. Tall, tan, and trim, with more salt than pepper, he poses for a few quick selfies with some fans — his being the kind of international fame that extends from American living rooms all the way to Malaysian bellmen.

Bourdain is in Kuala Lumpur to film Parts Unknown, his food-and-travel show that airs Sundays on CNN and is probably the best thing on TV in either of those genres. Last year, the show won a Peabody and three Emmys. Now going into its sixth season, the show is much replicated at its own network. "CNN has made a concerted effort to move into original documentary-style programming, and Parts Unknown is the cornerstone and flagship of that strategy," says CNN president Jeff Zucker. "It's the most-watched show on the network."

Who would have guessed 15 years ago that this self-styled rebel, who wrote about waitress blow jobs and shooting heroin in his best-selling 2000 memoir, Kitchen Confidential, would become America's contemporary answer to, say, Mark Twain — our most enthusiastic chronicler of life outside our borders? It's a success story even more impressive for its unlikely trajectory: from New Jersey–bred college dropout to talented, if unheralded, cook to celebrated writer to TV star. And no one is more shocked by it than Bourdain.

"Hey, Tom," he says as one his young producers, Tom Vitale, walks up. On Bourdain's first show, A Cook's Tour, in 2000, he and his executive producers scouted everything themselves, with occasionally dicey results (their visit to a Khmer Rouge minefield, for instance). But now that Bourdain is the very valuable head of Bourdain Inc. — an ever-growing empire that includes three TV shows, a publishing imprint, a travel website, and soon, a gargantuan Manhattan food bazaar — he barely has time to eat lunch in all the cities he visits, much less to wander around in them. That task now falls to guys like Vitale and Jeff Allen, another producer, who have been in Malaysia for the past week, shooting B-roll of monkeys and nightclubs.

The van crawls 10 minutes through rush-hour traffic to Hakka, a Chinese restaurant chosen mainly for its proximity to the hotel. (Although to be fair, it does have a four-star rating on Foodpanda, Malaysia's version of Seamless.) We take a table on a sprawling patio under the only sliver of sky not blocked out by skyscrapers, with paper lanterns and twinkling Christmas lights strung from the rafters. Bourdain orders for the table: steamed crab, pork ribs, salt-and-pepper baby squid, pork fried rice, prawns with chili. A young woman in a white minidress pours him an Asahi, and he leans back in his chair. "So what's the plan?"

Bourdain hasn't been to Kuala Lumpur since December 2005, when he filmed an episode for the first season of his previous show, No Reservations. "Generally when we go back to places, we try to do it a different way," he says. But here he's intentionally revisiting the same old territory. "I'm an overly sentimental guy," he explains. "I'm not above wringing that for some bathos." He'll spend the next 48 hours eating and catching up with the friends he met back then, then fly to Kuching, in Borneo, where he'll catch a boat up the Skrang River and spend three days in a longhouse during the Malaysian rice-harvest festival. "It's going to be three days of savage drinking," Bourdain says. The last time he was in Borneo, he started downing tequila shots and rice whiskey at a bar, and by the end of the night was so obliterated that he propositioned the owner of his hotel. The next morning, one of his producers had to literally break down the door to his room and drag him to the airport.

(In a Kuala Lumpur food market in May. Photograph by Annabel Mehran)

"Wait a second," Bourdain says suddenly alarmed. "Where are we staying?"

Vitale laughs. "It's a different hotel." Bourdain looks relieved.

"Are you not eating, Tom?" Bourdain asks as the pork ribs start to circulate. "I wish I'd known — I would have ordered less food." Vitale says he's fighting a stomach bug he contracted a few days ago. "What happened?" Bourdain teases. "Did you have a salad?"

It's gospel among the crew to never order a salad when you're in the field. During a show they did in Haiti after the 2011 earthquake, one of his producers broke this rule; Bourdain waited until he was halfway through his meal to remind him about the cholera epidemic — cholera being transmitted via water, water being the typical way to wash salad. (The guy immediately went to throw up.) Vitale, who's filmed nearly a hundred shows with Bourdain and says he's gotten sick only three times, insists he's never ordered a salad in his life; he thinks it was from an iced coffee. But Bourdain is dubious.

"Wait a minute," Bourdain says. "Did you eat at the hotel?"

Vitale looks ashamed. "I knew it!" Bourdain says. "You never eat on the plane, and you never eat at the hotel." He shakes his head. "Oh, Tom."

Peninsular Malaysia, which sits between the Bay of Bengal and the South China Sea, is composed of three constituent cultures: traditional Malay, South Asian, and Straits Chinese. It's the kind of spot that Bourdain loves, ethnically and linguistically jumbled crossroads like New Orleans, Bahia, and Marseilles. "Monochrome is not that interesting to me," he says the next morning, sipping teh tarik in the Little India coffee shop, wearing the same jeans and boots and some Steve McQueen–ish Persol shades. Before long a local production assistant comes over and politely interjects. "I'm sorry to interrupt — Tony, they're ready for you."

Bourdain is not a man who likes to wait around, and he has organized his production so that he doesn't have to. There are no personal assistants, no wardrobe, no makeup. (Chris Collins, the co-executive producer of the production company behind all of Bourdain's shows, Zero Point Zero, jokes that their version of grooming is using a Leatherman to clip Bourdain's errant nose hairs.) Bourdain calls his crew — three producers and two cameramen in mobile E-Z Rigs — his Quick Reaction Force, and they're excellent at capturing the feel of a location while remaining respectful and unobtrusive.

"I've said a million times that I'd rather miss the shot than disturb the mojo," Bourdain says. "If you're stopping people to move a light, it fucks up the dynamic and the spontaneity. You end up with a show that looks like everybody else's."

CNN approached Bourdain about doing the series that would become Parts Unknown three years ago, when his deal with the Travel Channel for No Reservations was expiring and he was hesitant to re-sign. As a test, Bourdain says, he sent CNN "four of our most fucked-up episodes, the ones Travel hated most"; the network loved them. Bourdain says he'd been frustrated at Travel because he could no longer do the shows he wanted to do: For instance, they'd booked a Congo episode for season seven, but a few days before they were set to go, the network told him he couldn't. CNN not only promised to get him into Congo, they later got him into Cuba and the West Bank as well. Over the past five seasons, Bourdain has explored income inequality in Jamaica, a heroin epidemic in Massachusetts, and political repression in Iran. "On A Cook's Tour, there had to be food in every scene — I was a chef, and this was all I knew," Bourdain says. "Now my leash has gotten much longer."

ALSO: A Drunken Afternoon with Anthony Bourdain

"Once you leave the kitchen, the whole world opens up," he adds. "And it especially has for me." Now there are a lot of places on his list: Oman, Syria, Pakistan, Yemen. "We keep looking at Afghanistan," he says. "Apparently insurance is a real problem." Despite the common theme running through these places, Bourdain insists he's not chasing danger. "It's not about me in a fucking flak jacket, looking macho," he says. "Because I'm not."

When he started doing A Cook's Tour in 2000, Bourdain didn't know the first thing about making TV. "I didn't even know I had to look at the camera," he recalls. "I was like, 'You want me to talk?' " "He was so awkward and terrible," says Chris Collins, whose wife, executive producer Lydia Tenaglia, recalls a similarly unpromising start. "After our first scene on our very first show," she says, "Chris and I just walked out and looked at each other and said, 'We're fucked.' "

Now Bourdain relishes the process of putting together a show: tinkering with story structure, assembling footage. He has a standing challenge to the editing staff to see how long they can get away without having a conversation or voice-over in a scene, just ambient noise. "If I'm a dick about anything, it's postproduction," he says. He also hates going for the obvious when it comes to resolution. "When I make an hour of television, I don't know how I feel about it. I like complexity and ambiguity. I love to tell a story in a new and disturbing way." He pauses a moment to think of an example. "We did an Israel-Palestine show, and for a whole lot of reasons it was a difficult edit," he says. "And in an early rough cut, someone had the temerity to land on flowers growing in Act 6. 'Young buds . . . peace blooming . . .' " He makes a face. "I told them, 'There will be no fucking flowers growing in Act 6.' " And is that person fired now? He laughs. "Maybe."

Now Bourdain has started going further with the show, experimenting with color palettes and camera angles and ambitious cinematography. "What we do is, in a completely unsubtle way, rip off some of the finest filmmakers who ever walked this Earth," he says. They've shot episodes that borrow from Terrence Malick (Copenhagen), Wong Kar-wai (Shanghai), and Werner Herzog (the Amazon). Sometimes he even gets to collaborate with the very filmmakers he's stealing from, like Darren Aronofsky (Requiem for a Dream), who went with Bourdain to film an episode of Parts Unknown in Madagascar last season.

"It's superdark," Bourdain says of the episode. "The idea was to undermine the narrative process. You're always seeing my version, but I may not be telling you shit. Now we have Darren Aronofsky with us, and this really ugly episode happens that I gloss over in Act 3, and he revisits in Act 6. It's very unflattering. It does not make me look good.

And Bourdain was comfortable with that? "It was my idea," he says.

(Bourdain is opening New York's first Asian-style food bazaar next year. Photograph by Mark Seliger)

During his last trip to Malaysia, in 2005, Bourdain was, as he wrote in his book No Reservations, "in a very emotional, very shook-up place." "I was [at a] crossroads in my life," he said. "I was going to either come out of it alive and maybe a little bit smarter — or sink back into ever darker territory." Today he admits that he was going through some dramatic relationship troubles. He had separated from his first wife and was dating someone new, but "there was no question ever that it was doomed. I was prosodic — sick with love. And I was heartbroken. I think that's an underlying subtext to the whole episode."

Near the end of the episode, there's a scene in the Bornean village where he has to kill a pig for dinner, and the distant look in his eyes that follows is both haunted and haunting. "It was as far as I'd ever been from my previous life," he says today. "I was a man adrift after that. I didn't know what I was going to do next."

It wasn't long afterward that Bourdain met his now wife, a restaurant manager from Sardinia named Ottavia Busia, when they were set up on a blind date by his friend the chef Eric Ripert. By their third date they were getting matching knife tattoos, and within a year she was pregnant. During one crazy two-week span in 2007, Bourdain got divorced from his first wife, got remarried, and became a father.

Bourdain says that he never thought he'd have kids. "If I was sure of anything, it was that. But I've enjoyed every moment from conception until now," he says. "I loved living with a pregnant woman. I loved changing diapers. I love being the father of a little girl. There's not a minute of it that hasn't been awesome." He and Ariane, eight, cook together a lot — she loves making schnitzel and ratatouille with him. ("She has to stand on a little stool.") "She eats raw oysters, squid, and octopus," Bourdain says. "She's a pretty cool kid." Bourdain thinks she gets it from her mom. "My wife's side of the refrigerator is basically just liver and steaks," he says. "It's like living with a timber wolf."

Of course, the downside to having the coolest job on the planet is having to spend lots of time away from your family. Parts Unknown films more or less continuously from October through July. "The network breaks it into two seasons," Bourdain says, "but for me it's one year of shooting." During that time he's on the road for three weeks a month; before coming to Malaysia, he shot an episode in Marseilles, had three days in New York, then left again. When she was young, his daughter didn't mind it. "But now," he says, "she wants to know why. That's tough."

To make up for it, when he is at home, Bourdain turns into superdad. "I drop her off, I pick her up, I make Tupperware containers with school lunches all labeled and dated." During the summers, they rent a place on Long Island (in the part of the Hamptons "where they absolutely don't give a fuck about me") and "I don't see anybody," Bourdain says. "I don't go to a benefit, I don't go to a party, I never go to restaurants. My daughter decides what we do. Pool or beach, burgers or lobster."

Bourdain says that before Kitchen Confidential he never had health insurance, was always late on rent, was constantly dodging credit card companies. Needless to say, his standard of living has improved. "I'm not going to throw a water bottle at your head if I don't get my decaf mochaccino, but it's definitely true that I live a more comfortable life than I did 10 years ago," he says. "Back then I was younger and tougher, and it hurt less to sleep on a hard floor. Now, I like a nice thread count, I like a nice hotel, I like a nice shirt or a good jacket." But also, he says, "if I've been smart about anything, it's saying no to loads of shit" — meaning product endorsements and brand tie-ins. "A lot of people wouldn't be able to resist it."

He hasn't resisted everything. He recently filmed his first Hollywood cameo, playing himself in The Big Short, an upcoming financial flick directed by Adam McKay and starring Brad Pitt. There's also Bourdain Market (he insists his business partner chose the name), a huge (and hugely expensive) Asian-style food bazaar set to open in Manhattan next year. "It's not a food court; it's a real market," Bourdain says. "There will be butchers and produce and fishmongers. It will serve an important, everyday function. Its heart and soul will be Asian, but I've also been recruiting Mexicans, Peruvians, Brazilians. It's going to be independent mom-and-pop stuff they've been doing for generations, at an affordable price. As a proud New Yorker, I'm sort of pissed that we don't have it already. Why can't we have what Singapore or Hong Kong has? We're a huge, multicultural city, a melting pot. Do we not have enough Chinese or Mexicans to do amazing food from their homes?"

When he looks back on the guy who wrote Kitchen Confidential, or even the first few seasons of his TV shows — the chain-smoking 42-year-old in the leather jacket and Ramones T-shirt and gold earring — "I think immature is the word," says Bourdain. "Self-indulgent. Infantile. But there was also an arrogance that I'm proud of. I don't deny that guy; I'm not ashamed of him. I still see that guy all the time on the road, when people come up to me on the road and say, 'You used to be cool.' I get that! You're working for a living — you're cleaning out the fryer, serving 300 dinners a night. And look at what I'm doing. I totally respect that point of view."

Every morning in Kuala Lumpur, Bourdain is down in the lobby at 6:45 am to take the van to a local jujitsu academy for training. Bourdain started doing jujitsu about two years ago, after his wife — an aspiring pro who spends hours a day practicing moves like "face-cranking" and "knee-reaping" — got him to try a class by bribing him with Vicodin. Now he trains in every city he visits, from Okinawa to Budapest. Thanks to jujitsu, he's lost 30 pounds, gotten himself off Lipitor, and even kicked his two-pack-a-day cigarette habit. "If I smoke now, I will get my ass kicked," he says. "It's humiliating. I can't even make it through warm-ups."

Despite the physical benefits, Bourdain loves jujitsu for its mental aspect. "It's an exercise in problem-solving," he says. He's not spiritual about it: "All the good health and shit, for me, that's a by-product of the head game. It's much closer to writing for me. On a good writing day, I'll write myself into a corner, then spend the rest of the day trying to solve the problem I've created for myself. Jujitsu is like that. You get your ass kicked, spend the day thinking about it, then go back the next day to see if you figured anything out."

(Which is not to say he doesn't also enjoy the baser pleasures of a sport that features MMA-style submission holds from time to time. "When you're 58 years old and you feel a 22-year-old die in your arms — that's fucking awesome.")

ALSO: Bourdain's Life Advice

Bourdain, a white belt, is realistic about his jujitsu expectations. "I'll never be beating 28-year-old former college wrestlers," he says. "If I suck a little bit less than I did last week, that's enough for me." That said, he would like to enter a seniors competition someday — to show up at a tournament without having his name announced, "meet a stranger, and leave it all on the mat. But I don't want some fucking weightlifter coming out of retirement just for the pleasure of snapping my neck."

So far, knock on wood, he's been hurt badly only once. But it was a doozy: He tore his groin. "I heard someone scream, and it was me," he recalls, wincing. For a year he had to lie in bed for 15 minutes every morning, trying to figure out how to stand up without hurting himself. "There's a certain kind of muscle pain that is good for you," he says. "That is not it." Now his daughter — who's also started dabbling in jujitsu — likes to remind him before he leaves for class: "Remember, Dada — you're old."

In his last afternoon in Kuala Lumpur, while the five o'clock rains pour from the skies, Bourdain is in his hotel room writing a voice-over for the Ethiopia episode for the upcoming season. (He accompanied chef Marcus Samuelsson — an ethnic Ethiopian who was adopted by a Swedish family as a baby — back to his old village to explore questions of African identity. "It's an amazing episode," Bourdain says.) Then, after another quick nap ("I'm a big believer in naps"), it's back in the van to visit the Jalan Alor — one of the city's largest night markets — to film a scene and do some research for Bourdain Market as well.

Bourdain spends an hour being filmed strolling up and down the street, checking out the mountains of durian and jackfruit, the stalls overflowing with stacks of chicken satay. He grabs a plastic table near the street and orders a Tiger beer and a huge dinner for one, a parade of entrées he samples for the cameras. "That's black-pepper crab," he says, pointing. "That's char kway teow. And I don't know what the fuck that is, but it's delicious."

Bourdain says there are two things he loves about Parts Unknown. The first is the technical satisfaction of creating something, "of being involved in a process that results in a thing." The second is learning. "Knowing a little more than I did last week. Progressing in some incremental way." He points to a tattoo on his arm, a quote from one of the Greek skeptics. "This says, more or less, 'I am certain of nothing,' and that's how I feel. I'm pretty sure that cheese and sausage are good. Other than that, it's a world of confusion and uncertainty."

One of the less-observed facts about Bourdain — yet also a central part of his appeal — is that he's actually not all that worldly. He speaks a little French, enough to get by at a restaurant, and he knows enough Italian to understand when his wife and daughter are making fun of him. But beyond that he has no language expertise, and he'd barely traveled out of the country before he filmed A Cook's Tour. "I'd been to France a few times, and the Caribbean and Mexico, but that was it," he says. "I hadn't even been to L.A. until my book came out."

There are some places Bourdain knows a lot about, like Vietnam or Japan, where he often returns. "But there's other places where I'll say fuck it and just wing it," he says. "The audience learns as I learn." It's his innate curiosity, his willingness to engage and admit his ignorance that helps make the show so appealing. Bourdain says he enjoys the feeling of dislocation and is comfortable being lost in a strange place. "But there aren't a lot of those places left," he says. "I've been everywhere."

"But no matter how jaded you get," Bourdain says, "shit still sneaks up on you. Like looking out over [Saudi Arabia's] Empty Quarter when the moon is dropping over miles of dunes. Or whipping across rice paddies in Cambodia with Depeche Mode in my earphones. Bobbing around in warm, beautiful water in Brazil half-drunk, listening to samba in the background. My happiest moments on the show are when we've finished shooting, maybe had a couple drinks or a joint, and you look around and say, 'Wow — who gets to do this?' At those moments, life does not suck. Even just grabbing some noodles with the crew. A not-on-camera bowl of noodles," he says, smiling. "That's perfect happiness."

(With his wife Ottavia in Miami in 2014. Photograph Courtesy Ottavia Busia)

By now Bourdain has reached a point where almost anything he can dream up is within reach. So what's still left to try?

"I'd like to do a show with Keith Richards," he says. "Go back to the château where they recorded Exile on Main Street. Make a meat pie with him. I have reason to be optimistic." He's currently working on a cookbook, which he promises will be — visually, at least — "the most fucked-up cookbook ever." (Longtime Hunter S. Thompson illustrator Ralph Steadman is doing the cover.) And though he recently tossed out a crime novel he'd been toiling away at for years, he'd like to write more for TV — as he did quite skillfully for HBO's Treme, an experience he called "possibly the most fun of my professional career."

And how about nonprofessionally?

"There are moments I'd like to have," Bourdain says. "I'd like to eat pasta out of a chipped bowl in Tuscany. I'd like to go to Paris with my daughter when she's old enough to really get it. There are a bunch of books I'd like to tackle. Don Quixote. Joyce. And I'd like to putter — puttering would be good. Make bad sausage. Grow horrible tomatoes. Make terrible wine I could inflict on my houseguests. That would please me."

At the night market, after filming wraps, the crew starts loading up the van. But it's only about 9:30 and Bourdain doesn't want to go home yet. He tells the producers he'll meet up with them later and strolls over to a side block filled with neon-lit foot-massage parlors. His eyes light up. "I love this shit," he says. He spots one that looks appealing ("the key is to find a place with no attractive people — just old, fat Chinese men") and steps to the door. "You want massage?" the lady asks.

"Yes," says Bourdain. "Yes, we do."

Five minutes later, Bourdain is horizontal in a leather recliner, sipping water from a plastic cup and having his feet annihilated by a tiny Malaysian woman while WWE wrestling plays on a TV in the background. There are no cameras in sight. "You know how we were talking about those little moments earlier?" Bourdain says. "Well this is one." Eyes closed, he smiles. "I'm a happy man."