He is the author of A Ticket for Perpetual Locomotion, a novel about a young man named Carlos who disappears after reading the work of fictitious Mexican writer Eduardo Maranda. Short, episodic chapters follow the adventures of three 'Perpetual Locomotors' and Maranda, the author of their troubles. The novel uses a multiple narrative and frequent flashbacks and has elements of magic realism, mystery and travel genre. It was published by Interactive Press in 2005 with the support of the Australia Council and won the 2005 IP Picks Award for Best Fiction. A Sydney Morning Herald reviewer said the book was "nothing if not ambitious" but "too heavy to keep the reader moving."
Short stories by Gates have appeared in such academic journals as Verandah, Dotlit, Gangway, UQ Vanguard, LINQ and Southerly.