Mens han flyr flyet sitt, oppdager Tails en liten øy og lander for å undersøke. Mens han først ser ut til å være ubebodd, kommer han til slutt over en gammel kvinne. Hun erklærer seg selv for å være den store heksevognen, og hevder øya og alt på den som sin egen, og truer med å forvandle eventuelle dissidenter til krystall. Hun drar deretter avgårde med håndlangerne sine, og Tails, fast bestemt på å stoppe henne, jager etter dem. Det er ett av to håndholdte spill på Game Gear som har Sonics sidekick Miles "Tails" Prower som hovedperson. Spillet følger eventyrene til Tails mens han prøver å redde en øy fra Witchcart, som hevder å være i stand til å gjøre meningsmotstandere til krystaller med sin magi. Det ble opprinnelig utgitt 28. april 1995 som et eksklusivt spill til det japanske markedet. Imidlertid så Tails' Skypatrol senere en utenlandsk utgivelse da det ble inkludert som et opplåsbart minispill i Nintendo GameCubes Sonic Adventure DX: Director's Cut, og ble utgitt på nytt som et av de omtalte spillene i Sonic Gems Collection.