"Far from Yokohama" features a Japanese couple (Youki Kudoh and Masatoshi Nagase) on a cultural pilgrimage, "A Ghost" focuses on an Italian widow (Nicoletta Braschi) stranded in the city overnight, and "Lost in Space" follows the misadventures of a newly single and unemployed Englishman (Joe Strummer) and his reluctant companions (Rick Aviles and Steve Buscemi).

The narratives are linked by a run-down flophouse overseen by a night clerk (Screamin' Jay Hawkins) and his disheveled bellboy (Cinqué Lee), the use of Elvis Presley's song "Blue Moon",[3] and a gunshot.

The starting point for the script was the ensemble cast of friends and previous collaborators Jarmusch had conceived characters for, while the tripartite formal structure of the film was inspired by his study of literary forms.

Mystery Train's US$2.8 million budget (financed by Japanese conglomerate JVC) was considerable compared to what the director had enjoyed before, and allowed him the freedom to rehearse many unscripted background scenes.

Mitsuko is obsessed with Elvis, and has put together a scrapbook detailing her belief that the singer has a mystical connection to other cultural figures ranging from Madonna to the Buddha to the Statue of Liberty.

[12] Unlike the jovial Steve Buscemi, Strummer did not stay on set to joke with the veteran actors between shots, but instead preferred to keep his own company, focusing intensively on orienting himself to the role.

[11][13] Repeat Jarmusch collaborators who worked on the film included John Lurie who provided the original music, cinematographer Robby Müller,[15] and singer Tom Waits, who in a voice appearance reprised his role of radio DJ Lee Baby Sims from Down by Law.

[7] This motif of flashes of red was later described by Suzanne Scott of Reverse Shot as "giving the impression of a failed attempt to grab a bit of Elvis's glamor and try it on for size, only to inevitably discover that it looks cartoonish out of context".

[11][23] At a Memphis nightclub with the Japanese actors during production, the director had Masatoshi Nagase – who spoke little English but was an accomplished mimic – try chat-up lines on the female clientele as an acting exercise.

[33] The DVD release was criticized by Anna Lazowski of AllMovie who awarded it two stars out of five compared to four for the film itself, citing the paltry special features of 24 scene selections and a collectible behind-the-scenes booklet.

[38] Robert Fulford of the National Post hailed it as "eccentric and deliriously funny",[39] while Rolling Stone's Phil Whitman remarked that the director's "bracing, original comedy may be mostly smoke and air, but it's not insubstantial".

[18] In The New York Times, Vincent Canby called it "thoroughly fascinating, a delight" and the director's best effort to date, drawing note to its retention of the "same kind of dour, discordant charm" exhibited by Stranger Than Paradise.

[19] He praised Jarmusch's development as a screenwriter – citing the restrained dialogue, humor and subtlety of the narrative and the careful construction of the plot – and the performances he elicited from the ensemble cast.

[19][40] John Hartl, in The Seattle Times, also drew a comparison with Stranger Than Paradise, judging Mystery Train to be the more accessible work while retaining the dry wit of its predecessor.

[41] Of the film's characters, critic Jonathan Rosenbaum of the Chicago Reader wrote that some were "beautifully imagined and realized, while others seem drawn from a more familiar stockpile, designed for reuse rather than discovery".

"[42] This reproach was echoed by other reviewers who found that the film's style did not stray far from that of the director's earlier work – a critical backlash that would be amplified two years later following the release of Night on Earth (1991).

[28][43] Postmodern cultural critic bell hooks cited the interaction in the Memphis train station between Thomas and the Japanese couple as one of the few examples of nuanced, deconstructive and subversive treatment of blackness in American film.

[46] In an April 2000 retrospective of Jarmusch's work for Sight & Sound, Shawn Levy concluded that the film was "as much a valentine to the allure of the American way of pop culture as it is a cheeky bit of structural legerdemain without terribly much resonating significance".