By his mid-30s, director Luc Besson had earned a reputation for art-house hits like The Big Blue and La Femme Nikita, and even made inroads in Hollywood with the Jean Reno/Natalie Portman thriller The Professional. But he’d never attempted anything in the realm of big-budget sci-fi — even though The Fifth Element was in many ways his first love, dreamed up when he was still a teenager: the fantastical tale of a taciturn New York cabbie-turned-guardian of the galaxy; a beautiful, inscrutable Supreme Being; and one very special set of stones.

LUC BESSON (WRITER-DIRECTOR): At 16 I wrote three stories. I wrote 200 pages, and it was bad. I wrote 200 more, it was still bad. [Laughs] So I throw it away and I try again. You have to understand: At the time I’m living 60 kilometers from Paris, almost in the middle of a forest, with a stepdad who doesn’t want music, TV, nothing. So I’m very isolated. And basically you have three solutions. The first is you become alcoholic, the second one is you kill yourself, and the third one is you escape with your pen. Fifth Element was the perfect escape.

IAIN SMITH (CO-PRODUCER): Initially, the idea was to make two films. The cost for both, I think, came to something like $150 million. So after some discussion, Luc decided that he wanted to conflate the two scripts into one.

BESSON: Everyone in L.A. was saying, “Oh, if you don’t have a star, you can’t make the film.” But we didn’t even try to go to Bruce Willis, because he was too expensive. And then I have lunch with [Willis’ then wife] Demi Moore, and Bruce shows up at the dessert and he just says, “Hey, my man, what about me?” [laughs] and I tell him [about the money]. He said this very sweet line: “If I like it, we will make an arrangement.”

BRUCE WILLIS (KORBEN DALLAS): He came out to our house in Malibu. I just liked Luc — I liked the story, I liked the idea. I thought it would be fun to go to France and make a movie.

BESSON: When I started this film, I knew I had a 50 percent chance that after this I will not be in the movie business. You cannot write a sci-fi that is funny, first of all, made in France with Jean-Paul Gaultier [designing costumes] and the hero is a woman. And then you know what? She speaks a language no one understands! When you start that way, why not take all the risks?

SMITH: For [the character of] Leeloo, Luc saw thousands of models and actresses, women from all over the world.

BESSON: The first time I met Milla was in New York, and she was overdressed and over-made-up and very, very nervous. She was petrified.

MILLA JOVOVICH (LEELOO): I thought I did great! I was really happy with the way the audition went. But, you know I had on, like, green eyeshadow, white patent-leather platforms, my little minidress. I was 18 and just thought I was the coolest thing in the world. And I was so excited to meet Luc, because I was such a huge fan.

BESSON: She sang a little song, we took a tea, and it was nice, but I didn’t feel it. Then a few weeks later at Chateau Marmont [in L.A.], I went to the swimming pool and guess who I see in a white T-shirt and jeans, without shoes, no makeup, and a ponytail? Milla!

JOVOVICH: Of course I was like, “I need to change!” But he didn’t want to give me the opportunity to put all my makeup back on. [Laughs] So I went and saw him later, and he put me on tape again. He had me do some really crazy stuff, like dancing with no rhythm, singing, speaking in gibberish. I didn’t understand any of it, but I was game.

BESSON: She was perfect. I was so seduced by the test that she did.

SMITH: Luc said to me at one point, “You realize that whoever I cast as Leeloo, I have to fall in love with them.” And I understood what he meant by that. He didn’t want just some pretty girl, he wanted someone with that particular individual thing that Milla had.

JOVOVICH: It was sort of a My Fair Lady situation, because I was really learning to be a completely new person. Where normally I would have been reading a book or talking on the phone or hanging out with my friends, I was at the zoo at the animal cages, like, imitating the lions and the birds and the wolves. I spent months in this kind of seclusion, going from one lesson to another — acting and movement and dance and fight choreography.

CHRIS CARRERAS (FIRST ASSISTANT DIRECTOR): Luc took her under his wing and protected her from everything.

BESSON: That language, I wrote a dictionary with 500 words. But we were the only two who spoke it on the set. She had to learn it, and then we could talk to each other in it.

JOVOVICH: It was really interesting, the fact that there weren’t going to be subtitles.

SMITH: We the audience are experiencing Leeloo through the eyes of Bruce, so when he fell in love with this weird woman saying this weird stuff, it was important to have their curiosity aroused.

CARRERAS: We liked that. If you understood what she was saying, it would diminish her. But it was a real language; it wasn’t just gobbledygook.

With Willis’ action hero Korben Dallas and Jovovich’s supreme being in place, there were other roles to fill, including unhinged villain Zorg and outrageous radio host Ruby Rhod.

BESSON: For Ruby, I met Jamie Foxx and Chris [Tucker] the same day. They were both adorable and so sweet, and I loved them both. But the fact is that Jamie at the time already had lots of muscles. Chris, he looks like a shrimp next to Bruce, and it’s way more comic to have a character who is thinner and more fragile. So I chose him.

CHRIS TUCKER (RUBY RHOD): They were really protective of the script. They didn’t let anyone know what the part was, so I was always asking, “What is the movie about?” I’m this young kid, real scared. Like, I don’t know if I can do this.

BESSON: Prince was actually supposed to do the part before Chris. But it was a nightmare, because he’d give you an appointment and then he comes, like, seven days late. [Laughs] And sometimes he shows up when you don’t expect him. You can’t grab him, you know? He was free and he wants to stay free. But when you think about Prince and then you watch the film, you feel there is a flavor.

TUCKER: I saw Prince in a club after the movie came out, and he told me he was supposed to play the part but that the clothes was a little bit too much for him. “I was like, ‘What?!'”

SMITH: Chris came in for a lot of flack in America. A lot of people couldn’t get the floating gender thing, the high-pitched voice. But he really got the energy — that very particular kind of gender-liberated, anything-goes thing that Prince did. We needed that to carry the film through the middle parts, especially with the battle in Fhloston Paradise. He had to do a lot of reacting at a very high level to make those scenes work.

TUCKER: I remember going to London for the fitting, them showing me all the clothes for my part and I was kind of like “Whoof, this is a deep, deep character.” [Laughs] Luc is talking in French and he’s talking in English about what he wanted with the clothes and the hair and then I think he wanted some lipstick, and I was like “Whoa, man!” I’m this young kid, really scared, like I don’t know if I can do this. But all that stuff really helped me get into character.

CARRERAS: Gaultier would have to vet every single person, every single extra. That’s how intense he was in the look of it.

JOVOVICH: Listen, if there was ever a time to feel comfortable wearing bandages, it’s when you’re 19 and in the best physical shape of your life. [Laughs] Okay yes, there’s this inadvertent sexuality from the nature of the costume, because that’s what makes it iconic as well. It has to be beautiful, it has to be sexy, But Luc and I talked about it a lot — at first [Leeloo]’s naked, and they need to put as little on her as possible because they need to do injections and take samples from her. It’s medical. So we came up with this bandages idea, and Gaultier just did such an amazing job interpreting that.

TUCKER: I didn’t even know anything about Gaultier, I was so young. Then I found out later that he’s like the biggest designer in Europe, and just the coolest.

WILLIS: I liked the stuff that I wore, that Gaultier. I thought it was pretty cool. One of the things I remember is that Luc had for some reason dyed his hair blond. And I said, “You know what? I should dye my hair blond, have a little wig on my head.” That was a contribution of mine, and he liked it.

Filming with the actors began in January 1996 on soundstages at Pinewood Studios near London, with a primarily French and British crew.

CARRERAS: Luc was interesting. Everything was done in French even though he spoke English. And he used to refer to his sets as his bathroom, as in, he doesn’t like a lot of people in his bathroom. [Laughs] That was rule number one. And the pace was very quick, because he knew exactly what he wanted.

BESSON: Every time something was too classical, like the villain seeing the hero at the end and they fight — no way, let’s change it! That’s the fun of it. And you don’t know how many people told me, “You cannot put the president as a black man.” Really! Of course, it was 20 years ago…. With Gary [Oldman, as the villain], it was a friendship and collaboration. I wanted to produce his film Nil by Mouth on the one hand, and I had the role for him in Fifth Element on the other hand. I ask, “Do you want to do Zorg?” and he said yes, he was happy to do it. It took some time to get the voice of the character, because he’s so extreme, Zorg. So finally he proposed this sort of half-Texan accent and it was very funny. He was coming for one or two days of shooting [for us] and then he went back on his set. Some nights we would watch the dailies of both movies together.

WILLIS: Gary and I talked, and I said that I wished we could have had more scenes together. We had one brief moment in the film where I walk past Zorg’s office, and that was about it.

SMITH: Gary does those little moments so well, the humor. “There are no stones!” We wanted to be afraid of him, but we couldn’t make him trite, you know?

JOVOVICH: Luc was very secretive with Leeloo. Bruce had met me, obviously, but the first time he saw her in costume was that scene where she falls into his taxicab. Luc shot it with two cameras so you could really get that first reaction.

WILLIS: Of course I remember that. I never looked at it as a romantic moment, though. I would have to swear you to secrecy, because the real romance was between Luc and Milla. By the time I had gotten to Paris they were already kind of smitten with each other.

SMITH: Luc is a very active guy and he’s passionate and all that entails, so we didn’t find [their relationship] that surprising at all. It meant that the performance Milla gave was invested with the love, if you like, that they had.

CARRERAS: People weren’t talking about them in a gossipy way, but you could see there was a connection, shall we say. [Besson and Jovovich were married in 1997, and divorced in 1999.]

JOVOVICH: Chris [Tucker] and I, we were having fun. We got along because both of us were from the West coast — West coast in the house! Everybody was going out together and clubbing.

TUCKER: Milla was so sweet, so nice. I was young and bored and homesick so I went out a lot. We hung out on the set too, because there was a lot of big [scene] changes and a lot of shooting, so we had downtime.

WILLIS: There wasn’t much conversation between me and the other characters. I was just trying to save the world.

TUCKER: I was a little afraid to talk to Bruce too much. I was like, “Damn, it’s Bruce Willis!” I didn’t want to mess up anything and get fired. So whenever he said something, I just tried to answer real quick and then move on. But he was really cool.

JOVOVICH: Demi was on set a lot, and she was rad. I would babysit for them sometimes when I wasn’t working. I was so young, I probably had more fun with his kids at that time. [Laughs]

WILLIS: We had long days, and we’d just have to work and work and keep it moving quickly. Luc does a lot of takes. But that’s part of the film business, and I didn’t have any problem with it.

JOVOVICH: Luc wanted to get to a place where people were doing stuff they weren’t supposed to do and surprising him. This one poor girl, she did I think something like 87 takes, and she was just one of the stewardesses!

SMITH: Luc got Bruce to give a very unusual performance. He’s normally carried along by testosterone, you know, but I think he loved it… Guys [like him] challenge directors all the time, because it’s their way of finding out if the director really knows what they’re doing. Ridley Scott can handle it, Darren Arronofsky, George Miller. But I’ve seen other directors just fold. They cannot deal with the onslaught a major star brings. And Gary was no slouch either, he was at Luc pushing too. [Laughs]

Besson used hardly any CGI, which meant the production was physically much larger and more complicated.

BESSON: Technology today is so easy that you can do whatever you want. At the time it was a nightmare. But we used, I think, only two green-screen shots in all of it.

JOVOVICH: Even when it’s a green screen, the worlds were still being put into my head. Every time Luc panned the camera on me standing on the high rise when I see New York for the first time, he would yell out “There’s a dinosaur running at you!” or “You see medieval Europe and cannonballs!” Or “You see China!” He wanted to see a real reaction and have me really visualize what was going on.

CARRERAS: It was great fun. You could see the madness of the film, and how eclectic it was with all the different sets and costumes and lighting and all the different creatures and characters. It was a bit like Star Wars, but better. [Laughs]

SMITH: A lot was done with model miniatures. The New York set we built in Venice, in California. Fhloston Paradise as well. But they’re not small things — they’re big, big miniatures, if you follow me.

CARRERAS: The Fhloston explosion was one hell of a big bang. Or as Milla would say, “Bada-bang. Big boom!” [Laughs]

NICK DUDMAN (CREATURE DESIGN SUPERVISOR): We had a whole team looking after the [aliens]—people with electric fans pumping air, making sure their fluid levels were kept up and those heads came off between takes. The Mangalores couldn’t see out because of their masks, so we had to fit each one with a camera, a monitor, and a TV screen inside with links to my crew who literally went, “Walk, walk forward, shuffle, shuffle, for God’s sake, STOP!”

CARRERAS: I did the first four Harry Potters and I’ll never forget having to hold a golf ball or a tennis ball at the end of a stick and trying to tell everybody “This is a dragon!” or “This is Voldemort” or whatever. This was a one-off. The diva scene, we basically shot it like a concert. The curtain came up, and that was it. It was a bit jaw-dropping, I have to say — the first moment when that voice comes out, that first note. I’d not seen the outfit or the choreography [together]. And to witness it for the first time was absolute goosebumps.

DUDMAN: The diva was particularly difficult to make. We ended up with [actress] Maïwenn on 14-inch stilts wearing a skintight foam and latex dress that had to be made in one single piece with no seams… Luc didn’t want to the actors to see her before her entrance, so there was a lot of smuggling things down the corridor in the back, going “Where’s Bruce?” and all that. It was nerve-wracking, shooting at night in the opera house, worrying about whether the latex going to peel off, or if she stepped forward too far on the stilts would she just scream and disappear into the orchestra pit? There were lots of worries. [Laughs]… But intercutting it with the Mangalore fight scene was just fantastic.

JOHN AMINICELLI (POST PRODUCTION SUPERVISOR): In those days you had to physically transfer the negative, so I arranged to have it safely flown to California. Then I get a call saying I should come to LAX. We were escorted into a little room where they brought multiple trashcans of negative that had fallen out of the airplane onto to the tarmac and had been run over by a forklift. That was the diva scene — like, one of the money shots. It was the one thing you absolutely did not want to have happen. But we managed to save the negative and cut it together get what Luc had wanted all along. That never happened to me on another 45 films.

Shooting wrapped in June 1996, and the movie debuted the following May at the 1997 Cannes Film Festival.

CARRERAS: If I remember, on the last day Luc sort of walked away, because he didn’t want to say goodbye. He didn’t want it to end.

SMITH: Bruce threw a party for the crew at the house we rented for him, and he played jazz for us. He’s a very, very good jazz musician. And I think that was his way of saying “Thank you, guys, it’s been a trip,” you know? … Bruce has a reputation for being quite difficult. He wasn’t difficult on this film.

JOVOVICH: Listen, this was still the ’90s. I guess you could say that was one of the last hurrahs of epic filmmaking in that sense — to be able to rehearse for four months and then to film for six months? That’s unheard of today, unless it’s like, a James Cameron film.

AMICARELLA: It was still a system that fostered creative values. It was still an era where features were features by definition, and we didn’t have all the format competition that you have now. We have vastly different challenges today.

DUDMAN: I build monsters for a living, and it was absolutely the most satisfying job I have done. I had a smile on my face from day one. Every day there was something slightly daft, something very entertaining, and in the end I think it produced a film that is not like anything else.

BESSON: When the film opened in the U.S., it was pretty slow. And then, like a miracle, people watch it again and say, “Oh my God, it’s different now, and I don’t know why.” And little by little, it became a cult movie.

AMICARELLA: The movie was comic book, it was Salvador Dalí, it was heavy metal. It was this cacophony, this vibrant palette of complementary colors. It was really different than, say, the original Blade Runner, which was more monotone and dystopian.

SMITH: There’s always disappointment when the reviews were lukewarm. I think part of that might have been Sony not quite knowing what they had on their hands, or how to promote it. We had exactly the same problem with Mad Max: Fury Road. Warner Brothers were puzzled and couldn’t really get it until the movie was made and winning Oscars and all that stuff.

BESSON: I respect the big machine, like Marvel and all this. But even if the films are pretty good, the fuel inside, the creativity — it’s not crazy, you know what I mean? So maybe a young audience, when they discover Fifth Element on DVD or whatever, they say “Oh my God, this is crazy.”

TUCKER: People come up to me and they always start with “You know what movie you did that I really like?”— like they discovered it. And they want to hear all the lines, yeah. I get “Bzzzz!” a lot… Could I wear those costumes again? Maybe. I don’t know if I could fit in one. I’d have to work out a little bit. [Laughs]

JOVOVICH: When I watch Leeloo, I don’t even see myself. It’s a different person altogether. And I tell you, once you have kids it all changes. Our bodies change. So I’m very happy that she’s there to remind me of my days when I was this magnificent being, youthful and just full of so much potential. I’m very lucky that I met her, that she was a part of my life for the short time that she was.

WILLIS: I haven’t talked about the movie since we finished. It’s not that it’s not something in my memory — it was a great cast and a great film. I just don’t really dissect the work that we do on a day-to-day basis.

BESSON: Would I make a sequel? No, no. For me there’s no point to go back to the same place. No matter how much you love a film, the fun is to try something else. Otherwise I’m going to do Fifth Element, Sixth Element, Seventh… And if I listen to people I will do Nikita 2, Nikita 3, Leon 2 and Leon 3. And that’s not interesting.

SMITH: It’s a fascinating thing, to see how the film survives. In fact, it becomes more loved by people as time goes on. And in the end, the movie is about love. That is the Fifth Element — it’s love that saves the world.