Mystery Train ma strukturę puzzli, jest rozsypaną układanką, której pełen obraz tworzy się w głowie widza. Akcja zbudowanego z pozornie niezależnych epizodów filmu rozgrywa się w podupadłym hotelu Arkada w Memphis w stanie Tennessee; rodzinnym mieście Elvisa Presleya. To tu zatrzymują się na chwilę bohaterowie opowieści: dwójka 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. Zamiast unieśmiertelniającego kultu i miłości do idola widzimy jednak tylko jego rozpaczliwe pragnienie zmartwychwstania.

Jak zwykle u Jarmuscha nie chodzi o akcję, fabułę, konflikty. Przeciwnie - reżyser ostentacyjnie pokazuje brak konfliktów lub ich pozorność, nic-nie-dzianie-się lub dzianie się pozbawione znaczenia i puenty. W przeciwieństwie jednak do wcześniejszych filmów, w których najważniejsze były ludzkie czyny i gesty, głównym bohaterem Mystery Train jest czas, bowiem Jarmuscha fascynuje możliwość pokazywania w kinie symultaniczności wydarzeń. Za to 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, Joe Strummera (lidera The Clash), nowojorskiej reżyserki Sary Driver, performera i muzyka Screamin Jay Hawkinsa, czy legendy bluesa Rufusa Thomasa.