Akcja zbudowanego z pozornie niezależnych epizodów filmu rozgrywa się w podupadłym hotelu Arcade w Memphis w stanie Tennessee, rodzinnym mieście Elvisa Presleya. To tu zatrzymują się na chwilę bohaterowie opowieści: dwoje japońskich turystów, podróżująca śladami swoich muzycznych idoli Włoszka, która w Stanach straciła męża, a także Amerykanka, która rozstała się właśnie ze swoim angielskim chłopakiem. Ich ścieżki przetną się na chwilę, a w tle rozlegnie się dźwięk wystrzału. Wszystkich nawiedzi też duch Elvisa.

Jak zwykle u Jarmuscha nie chodzi jednak o akcję. Przeciwnie – reżyser ostentacyjnie pokazuje brak konfliktów lub ich pozorność, niedzianie się lub dzianie się pozbawione znaczenia i puenty. Mystery Train ma strukturę puzzli, jest rozsypaną układanką, której pełen obraz tworzy się w głowie widza. Głównym bohaterem okazuje się tu czas, bowiem Jarmuscha fascynuje możliwość pokazywania w kinie symultaniczności wydarzeń. Podobnie jak inne jego dzieła, także to imponuje obsadą złożoną z aktorów i gwiazd undergroundu. Na ekranie przecięły się więc ścieżki aktora Steve’a Buscemiego, Joego Strummera (lider The Clash), nowojorskiej reżyserki Sary Driver (partnerki Jarmuscha), performera i muzyka Screamin' Jay Hawkinsa czy legendy bluesa Rufusa Thomasa.