Chef Nobuyuki Matsuhisa says that his restaurant in Los Angeles is lucky. If Oscar nominees come to eat there just before the ceremony, they tend to win. Robin Williams had been up for an award three times without success, but when he brought his family to Matsuhisa on the eve of the 1998 Oscars, Nobuyuki - more commonly known as Nobu - offered his congratulations in advance. 'He doesn't drink, but I sent a bottle of Cristal Roederer champagne over anyway, because I knew he'd win.' Sure enough, Williams walked off with an Oscar for Good Will Hunting. The following year Roberto Benigni was so pleased that the place had brought him luck that, after picking up his statuette for Life is Beautiful, he skipped the big parties to eat at Matsuhisa again. The whole restaurant, Nobu recalls proudly, stood up to applaud him.

Meanwhile, the Nobu restaurant on the first floor of Park Lane's ultra-fashionable Metropolitan Hotel was recently dubbed 'knickers-off Nobu' by the Evening Standard, who used the last few months' tabloid gossip to back up their claim that it is 'the randiest, sexiest, most lascivious restaurant in London'. At the end of last year, Bush singer Gavin Rossdale met Andrea Corr there; Gwyneth Paltrow was photographed kissing an unidentified man by the entrance; Rod Stewart's ex-wife Rachel Hunter stepped out with actor Mark Wahlberg; and Liam Gallagher and Nicole Appleton chose the restaurant for their first public outing as a couple. In January, England manager Sven Goran-Eriksson was seen dining there with his girlfriend Nancy Dell'Olio, while Harrison Ford - also recently separated from his wife - was there with a 'mystery blonde'. Dani Behr chowed down with J from 5ive, former escort of sporty Spice Girl Mel C, while David Coulthard effectively ended his engagement by dining with a girl who was not his fiancée, then going upstairs to share a bath with her. And of course, there was Boris Becker. He enjoyed a dinner at Nobu with Russian model Angela Ermakowa after Wimbledon in 1999 which led, in March 2000, to the birth of his daughter Anna. Prior to a court case in February, there were some nonsensical accusation involving stolen sperm, a turkey baster and a Russian mafia blackmail plot, but eventually the tennis star came clean: his baby was conceived in a post-sushi tryst in one of the Metropolitan hotel's linen cupboards.

As well as the luckiest restaurant in Los Angeles and the sexiest restaurant in London, Nobu's empire has expanded to Miami, Las Vegas, Malibu, Tokyo and Milan, with a thirteenth restaurant opening this month in Paris. If you want a weekend reservation at any of them, be sure to call several weeks in advance (unless you're a celebrity of course, in which case you'll have the number for the special VIP reservations line). Robin Leigh, the manager of the Park Lane branch, says he's been offered up to £1,000 by people desperate to get a table at short notice. Once inside, you'll be dining with pop stars, politicians, actors, supermodels and royalty, and although each restaurant is different, they all share similar attitudes. The design is always sleek and chic without being too formal. The food is light and healthy, but it's also elegant and reassuringly expensive. As for the service, Nobu is the kind of place where everyone knows who you are, but no one makes a great deal of fuss about it.

Celebrity party organiser Fran Cutler often eats at the Park Lane Nobu with her business partner Meg Matthews or other famous friends such as Kate Moss. 'It's very central, and it's not as uptight as a lot of good restaurants. You can dress up, but you don't necessarily have to. Celebrities like it because the service is great, but everyone gets treated the same. And the food is a whole experience: your tastebuds are pushed from pillar to post. They do a wicked mushroom salad, then you get the rock shrimps, the black cod, the saké with gold leaf in it ... There's always something different to try. You could eat there every night and not get tired of it.' It's a formula that has served its owner well. Listed in Forbes as one of the top five money earners in his profession, Nobu is on first-name terms with many of Hollywood's élite. He plays celebrity golf tournaments partnering Celine Dion. He has appeared in a Gap ad photographed by Herb Ritts. He has prepared private dinners for Bill and Hillary Clinton. He's even had a role in a big movie, playing a high-rolling Japanese gambler alongside Robert De Niro in the Las Vegas mob movie Casino. Thanks to his innovative cuisine and a chance meeting with an actor one night at the tiny eight-seat sushi bar in Matsuhisa, Nobu is the most famous sushi chef in the world.

Nobuyuki Matsuhisa was eight when his older brother took him to a sushi restaurant for the first time. It was about a year after their father, an architect, had been killed in a car accident. When Nobu passed through the sliding door into the restaurant, he says it felt like entering different world. 'The smells, the beautiful selection of fish The first time I went into a sushi restaurant, I knew my future - I wanted to be a sushi chef.' He started his rigorous seven-year training at the age of 18, getting up at dawn to go to Tokyo's vast Tsujiki fish market, then working in his mentor's restaurant until the last customers left at night, after which he cleaned up and slept on the floor. He got just two days a month off and earned a pittance. And he did this for three years before he was allowed to even start learning to make sushi. 'I had a lot of patience,' he says, 'because I loved this job. But I was enjoying it too. I like to see fish, and I went to the fish market every morning. I got to open the restaurant and see the customers. My mentor was making sushi, so I could watch him all the time. As he worked I'd be copying him under the table, just practising with my fingers.' When I ask what all this practice was for, what makes good sushi, he finds it hard to answer in words. The fish has to be fresh, he says. The rice has to be cooked perfectly. The combination of the two has to be harmonious, with the shaped rice matched exactly to the size of the fish slice. The entire bundle has to be packed together in a way that is not too hard, not too soft. But most of all, it has to have heart. 'I know the best way because I've been doing it for a long time, but to younger people, sushi means sushi rice, sliced fish. They make something that looks like sushi, but it doesn't have heart like mine.'

Nobu married after finishing his training, and soon after, in 1972, a Japanese-Peruvian businessman who came to the restaurant whenever he was in Tokyo invited him to come to Lima and open a traditional Japanese restaurant catering to executives at the big Japanese corporations with offices there. Nobu had always wanted to travel. There was a photograph he treasured of his father with some colourfully dressed local people in the Philippines. 'Whenever I missed my father, I looked at that picture and thought that one day, I'd like to go out of the country. It was a dream.'

For Nobu, happiness is directly linked to the quality of the local seafood. The fish was good in Peru, straight out of the Pacific Ocean. But after his rigorous training in Japanese cooking traditions that have scarcely changed for generations, he was excited too by the local cuisine, full of unfamiliar flavours such as garlic and chillies. The South Americans even had their own way of eating raw fish - ceviche, where the flesh is marinated in citrus juice. After three years in Peru, his partners asked him to economise on his ingredients and rather than compromise his art, he moved to Argentina. The fish was good there too, but the people weren't quite ready for sushi. A year later he went back to Japan, but after the big house, maid and gardeners they'd enjoyed in South America, life in a cramped Tokyo apartment was difficult.

So he took out a loan and moved with his young family to Anchorage, Alaska, where the fish was excellent. Money was tight so he did much of the building work for his new restaurant himself, as well as all the cooking. At the end of 1980, he took his first day off for months to celebrate Thanksgiving Day. He was at a friend's house enjoying a turkey dinner when the call came to say the restaurant was on fire. He got there in time to watch it burn to the ground. It's one of his worst memories, he says. There was no insurance, and nearly all the money he'd used to set up the place was borrowed. Thinking about Alaska can still reduce him to tears.

Heavily in debt, he took his wife and children home to Japan, then flew to Los Angeles alone to find work. Finally a friend lent him $70,000 to open Matsuhisa in 1987, a small, homely place with room for less than 40 people where he began to experiment with the rigid conventions of classic Japanese cooking, incorporating some of the ideas he'd seen in Peru. He began using garlic, chilli and coriander alongside traditional Japanese flavours like ginger and soy, and introduced new ingredients such as olive oil, truffles and foie gras. When a customer sent back a plate of sashimi, unwilling to eat raw fish, Nobu made a quick marinade for the slices and then poured hot oil over them, searing the outside so they looked more palatable to Western eyes: the 'new style sashimi' that remains on his menus to this day. Ruth Reichl, editor of the glossy US food magazine Gourmet, was then at the Los Angeles Times in charge of restaurant reviews. 'We had a critic who was married to a Japanese woman, they ate there in its first week and said it was extraordinary. It wasn't like sushi he'd ever tried before. She talked to Nobu in Japanese and got the whole Peruvian background. So he pretty much started out with getting amazing reviews.

'Americans have a huge appetite for sushi, but we also have an appetite for innovation. And for a very long time, he was the only one really playing with the form, taking a very traditional cuisine and doing innovative things with it. And then he quickly got a big celebrity clientele, which really fuelled it.'

Soon a place at the eight-seat sushi bar wasn't much easier to get than an Oscar nomination - and seemed to go to pretty much the same people. One night the director Roland Joffe came in with Robert De Niro, who he'd worked with on The Mission. In a voice that is still heavily accented despite his years in America, Nobu says he didn't recognise the actor: 'I didn't even know the name.' But De Niro liked the food, especially the black cod marinated in miso, and that night the two men ended up drinking together. After that, the actor would eat there whenever he was in LA. De Niro had taken over an old coffee warehouse in the run-down TriBeCa area of Manhattan with the aim of creating offices for film and media companies and a ground-floor restaurant. A year or so after they first met, he invited Nobu to look at the space. The chef went to hang out for a few days, but the memory of Alaska was too fresh for him to take the risk. Instead, De Niro eventually opened the successful TriBeCa Grill there with acclaimed New York restaurateur Drew Nieporent and a team of 24 celebrity backers that included Francis Ford Coppola and Mikhail Barishnikov.

Read the second part of the Nobu feature here