La Yorozuya d'en Gintoki i els seus amics (o millor dit, els empleats sota grans violacions laborals), en Shinpachi i la Kagura, viuen a la futurista i infestada d'aliens Edo. Accepten qualsevol treball que els hi ofereixen intentant no involucrar-se en coses massa perilloses. Però quan en Katsura, líder de la facció Joui rebel dels Amanto (alienígenes), i amic de la infància d'en Gintoki, desapareix després de ser atacat per un assassí desconegut, en Shinpachi i la Kagura comencen una investigació per esbrinar que ha passat. Mentrestant, en Gintoki troba una feina aparentment no relacionada, un ferrer anomenat Tetsuya li demana ajuda a en Gintoki per recuperar una estranya i poderosa espasa anomenada Benizakura, que havia estat recentment robada.

Les dues investigacions s'acaben creuant, i la Yorozuya acaba envolta en mig d'una conspiració contra el govern envoltada per la "màgia" de l'espasa Benizakura. Tot això acaba amb un enfrontament a gran escala amb vells aliats i enemics en la primera saga important i seriosa de Gintama.