The movie is composed of two stories that have little to do with each other except for a few casual run-ins when some of the characters happen to be in the same place at the same time. Both stories take place in Hong Kong.
The story begins with a hit man named Wong Chi-ming (Leon Lai) and a woman he calls his "partner." They hardly know each other and rarely see each other but she cleans his dingy apartment in club clothes and faxes him blueprints of the places he's to hit. Infatuated with him, she frequents the bar he goes to just to sit in his seat and daydream about him. One late night, Wong has a late night meal at McDonald's where he meets Blondie, a wild prostitute. While they spend time together, she has illusions that he's the ex-lover who left her for another woman. Wong's partner finds out about the relationship and puts a hit out on him when he tells her he wants to quit, ending the partnership they have.
Wong Chi-ming's partner lives in the same building with Ho Chi-mo (Takeshi Kaneshiro), a crazy delinquent who escapes prison. She helps him elude the police when they are searching for him. Ho is mute and still lives with his father. For work, he breaks into other people's businesses at night and sells their goods and services, often forcibly to unwilling customers. He keeps running into the same girl at night, Charlie. Every time they meet, she cries on his shoulder and tells him the same sob story. Her ex-boyfriend, Johnny, left her for a girl named Blondie. Together they play games to look for Blondie, go see soccer matches at the stadium, hang out in restaurants, and take rides on his motorcycle. He falls in love. Somehow they lose touch for a few months but they run into each other while he's masquerading as a business owner. She's in a stewardess uniform, mentally fit, and in a new healthy relationship. She seems to have forgotten all about Ho.Leon Lai as Wong Chi-ming / Killer
Michelle Reis as Killer's agent
Takeshi Kaneshiro as Ho Chi-mo/ He Zhiwu
Charlie Yeung as Charlie / Cherry
Karen Mok as Punkie / Blondie / Baby
Chan Fai-hung as Man forced to eat ice cream
Chan Man-lei as Ho Chi-mo's father
Toru Saito as Sato
Benz Kong as Hoi
Featured in the Fallen Angels soundtrack is a version of "Forget Him" sung by Shirley Kwan, a reworking of the classic by Teresa Teng, and one of the very few 'contemporary' Cantopop songs ever used by Wong Kar-wai in his films. In the film, the song is used as a message from the hitman to his partner. One track played prominently throughout the film is "Because I'm Cool" by Nogabe "Robinson" Randriaharimalala. It samples Karmacoma by Massive Attack. The Laurie Anderson piece "Speak My Language" is used as well.
The Flying Pickets version of "Only You" was used in the last scene of the film.
In the Chicago Sun-Times, Roger Ebert gave Fallen Angels three stars out of a possible four:
"It's kind of exhausting and kind of exhilarating. It will appeal to the kinds of people you see in the Japanese animation section of the video store, with their sleeves cut off so you can see their tattoos. And to those who subscribe to more than three film magazines. And to members of garage bands. And to art students. It's not for your average moviegoers—unless of course, they want to see something new."
Stephen Holden of the New York Times said:
"Fallen Angels is a densely packed suite of zany vignettes that have the autonomy of pop songs or stand-up comic riffs, all stitched together with repetitive shots of elevated trains, underground subway stations and teeming neon-lit streets. Although the story takes a tragic turn, the movie feels as weightless as the tinny pop music that keeps its restless midnight ramblers darting around the city like electronic toy figures in a gaming arcade."
In the Village Voice, J. Hoberman wrote:
"The acme of neo-new-wavism, the ultimate in MTV alienation, the most visually voluptuous flick of the fin de siécle, a pyrotechnical wonder about mystery, solitude, and the irrational love of movies that pushes Wong's style to the brink of self-parody."
Hoberman and Amy Taubin both placed Fallen Angels on their lists for the top ten films of the decade while the Village Voice's decade-end critics poll placed Fallen Angels at No. 10, the highest-ranking of any Wong Kar-wai film.
The film made HK$7,476,025 during its Hong Kong run.
On 21 January 1998, the film began a limited North American theatrical run through Kino International, grossing US$13,804 in its opening weekend in one American theatre. The final North American theatrical gross was US$163,145.
In 2004, Australian distribution company Accent Film Entertainment released a remastered widescreen version of the film  enhanced for 16x9 screens.
Kino International, which currently distributes the film on DVD, is planning a re-release of the film from a new high-definition transfer on 11 November 2008. Kino released the film on Blu-ray Disc in America in 2010.