Tre linee narrative diverse ambientate a Memphis: dei giapponesi (Masatoshi Nagase e Youki Kudoh) fanno un viaggio intorno ai luoghi di culto del rock; un'italiana (Nicoletta Braschi) è alle prese con apparizioni di Elvis Presley; una banda di criminali beoni e male in arnese (Joe Strummer, Steve Buscemi, Rick Aviles) compie una rapina.

Un film che non aggiunge e non toglie praticamente nulla alla poetica di Jarmusch, ma si limita a ribadirne in forma più o meno telefonata i tic e i contrassegni stilistici: il viaggio come condizione esistenziale, la peregrinazione come fuga dall'ordinario e dalle sue catene, un gusto per una comicità stramba e obliqua e, non ultima, una tendenza per la confezione del film a episodi che qualche anno dopo contribuirà a rendere il regista un'icona, anche di stile, grazie a Taxisti di notte (1991) e Coffee and Cigarettes (2003). Un insieme che rende Mystery Train – Martedì notte a Memphis un film jarmuschiano al cento per cento, ma a cui, però, non basta il marchio di fabbrica dell'autore per definirlo totalmente riuscito. Nessuno dei tre episodi ha infatti il mordente sperato, e si finisce con l'accontentarsi di un'atmosfera illuminata da uno spiccato senso critico, ma che appare a volte pigra e svogliata. Ruoli di rilievo per Joe Strummer, leggendario leader dei Clash, e Screamin' Jay Hawkins, autore della celebre I Put a Spell on You. La voce del dj radiofonico è di Tom Waits, attore che per Jarmusch aveva già lavorato in Daunbailò (1986).