Po fantastycznych "Wichrach Smoczogór" napisał trylogię krakowską – osobliwą mieszankę fantastyki, realizmu magicznego i historii alternatywnej. Publikował ponadto liczne opowiadania. Debiutował w roku 1999 na łamach "Nowej Fantastyki". Wielokrotnie nominowany do Nagrody im. Janusza Zajdla, otrzymał ją w roku 2008 za opowiadanie "Miasto grobów. Uwertura". Powieść "Chochoły" przyniosła Szostakowi z kolei Nagrodę Literacką im. Jerzego Żuławskiego.
W recenzjach jego "Wichrów Smoczogór" powtarza się sformułowanie "baśń filozoficzna". Akcja dzieje się w wyidealizowanej góralskiej krainie, w której rzeczywistość ukształtowana jest na podstawie baśni i gawęd. Zważywszy na pozaliterackie zainteresowania autora, nie powinno dziwić, że wiele z nich dotyczy muzyki.
"Ględźby Ropucha" w fantastycznych dekoracjach odtwarzają tradycję młodopolskiej baśni literackiej, takiej jak "Klechdy Sezamowe” Leśmiana. Ich styl jest wyrafinowany i metaforyczny, przypominający niekiedy twórczość J. L. Borgesa ("Księga"). Zbiór porusza problemy filozoficzne, traktując o religii, cudach czy fikcyjnym charakterze literatury. Nie oznacza to jednak, że opowiadaniom brakuje humoru – autor nie oszczędza swojemu światu ironiczno-melancholijnych komentarzy, zaś obowiązująca w nim waluta nazywa się... szostaki.
Do tematyki ludowej, już bez przekładu na fantastykę, Szostak powrócił w powieści "Oberki do końca świata". Jej narratorem jest przedstawiciel ginącej profesji – wiejski skrzypek Jakub Wicher. Akcja obejmuje czas od wojny do lat 90. XX w. i przedstawia przemijanie pewnej kultury. Książką tą Wit Szostak wpisuje się w tradycję tzw. prozy chłopskiej, co u stosunkowo młodego pisarza jest zjawiskiem intrygującym. Ciekawa jest również forma powieści, w którą wplatane są fragmenty autentycznych oberków. Jak mówi autor: "Muzyka, na oczach czytelnika, przechodzi w prozę".
Zupełnie inaczej przedstawia się trylogia krakowska. "Chochoły" opowiadają o rodzinie mieszkającej w krakowskiej kamienicy, a za sprawą możliwości, jakie daje fantastyka, miasto naprawdę staje się równoprawnym bohaterem powieści. "Dumanowski" to historia alternatywna o mężu opatrznościowym, bojowniku o wolność i naczelniku Rzeczypospolitej Krakowskiej, dzięki niemu istniejącej aż do 1918 roku. Jego wpływ jest przemożny: wieszczowie łamią przy nim pióra, obawiają się go zaborcy, a Polacy spoglądają nań z nadzieją. Tym śmieszniejsze jest zakończenie: Polska odzyskuje niepodległość zgodnie ze scenariuszem, jaki znamy z historii, tak jak gdyby Dumanowski absolutnie nic nie zdziałał. Można to interpretować jako gorzką diagnozę nieważności romantycznych mitów, jako że z nich ulepiona jest tytułowa postać. "Fuga" z kolei przedstawia niespójne, wykluczające się nawzajem wspomnienia starego Bartłomieja Chochoła, w których łączą się i zapętlają wątki z dwóch poprzednich powieści.
