They are a perfect match, which is the damnedest, most wonderful thing. Travolta’s been annoying, mostly, of late (Wild Hogs? seriously?) and Meyers has mostly been Indie Boy (his turn as King Henry VIII on Showtime’s series The Tudors is probably where most mainstream audiences will recognize him from, but even that’s a stretch, considering the select viewers for-pay cable series garner). It’s either sheer genius or pure dumb random chance that prompted director Pierre Morel (who gave us last year’s surprise hit Taken) to pair them up as odd-couple spies: the grungy, badass veteran and the stuffy, stylish newbie. Who’da thunk they’d spark with such chemistry? From Paris with Love may look, on the surface, like a lot of the same-old, same-old -- and it is, to be fair -- but part of what makes it feel so fresh is that you get the sense that Travolta and Meyers are inventing something invincibly new as they go along.

Want more fresh angles on the action buddy comedy? You got it. Screenwriters Luc Besson (you know him as the writer-director of the Transporter movies and The Fifth Element) and Adi Hasak whip up a lot that’s sorta breezy in, say, Reece’s girlfriend, Caroline (Kasia Smutniak), whom you would think wouldn’t be in on the fact that his job at the American embassy in the City of Lights (the Irish Meyers is playing American here) is just a cover for his trying-to-break-in CIA work -- man, does he want in to the inner sanctum of cool 007 shit! But she is. And she fine with it. One doesn’t like to spoil, and this really isn’t anything that ruins the many delightfully unkempt ragged edges that’ve been torn around the clichés, but look: She proposes marriage to him just before he goes off on his dangerous mission with Charlie Wax. And he’s totally cool with it. It may sound like a minor thing, but in a genre that is so dependent upon tradition -- even when it thinks it’s being dangerous and unbound -- this is a big step out of the box.

And Paris keeps on surprising you. The plot is, frankly, something of a convoluted mess about Chinese coke dealers and Pakistani terrorists skulking around Paris and getting up to a whole buncha no good. I didn’t have any trouble keeping up with things while I was in the thick of it -- it’s all a breathlessly exciting, surprisingly funny, nonstop 90 minutes of audacious twists, excessive violence, sexy car chases, and just plain cinematic tomfoolery -- if it cannot be denied that in the clear light of day, I don’t see where the connections are between the drug dealers and the suicide bombers. But that doesn’t matter. What’s cool is the effortless multiculturalism of the film -- Paris is a living, breathing world city here, and not just in its wide variety of bad guys, and nothing like the picture-postcard image we’re usually condescended to with.

And it’s cool, too, how Morel and Besson and Hasak balance, in exquisitely satisfying fashion, a story that is timely and pertinent -- the faith it takes to fuel suicide bombers and romantic love is key to the plot -- while also managing to stay refreshingly apolitical about it all. And the humor comes not from culture snarking -- the few jokes about France are not at the expense of that fine nation but in the honest expectation that it might actually do things better than America -- but from the interplay between our two heroes. If this is the birth of a new franchise, hoorah: it is pure movie joy to revel in the pure joyful movie-movie electricity between Travolta and Meyers, and I’d love to see more. And more movies like this one, that embrace the nonsense and the cheap thrills with full-throated abandon.