GraceLand's protagonist Elvis Oke recalls how when he was younger he and his friends used to evaluate the characters in Hollywood action films: they were all either John Wayne, the uncomplicated embodiment of good citizenship; Bad Guy, the equally uncomplicated embodiment of evil; or Actor, the ‘rogue’ who is ‘part villain, part hero’. By the time Elvis is 16 years old, however, the movies have changed. ‘Now dere is only Bad Guy and Actor. No more John Wayne’, his friend Redemption explains. The shift mirrors the anomie that has descended on Grace-Land's Nigeria: good citizenship is no longer a possibility; one must choose (or have chosen for one) either the sociopathic evil of Bad Guy or the uncertainty of Actor.

Throughout the novel, Elvis struggles with the latter and with what it means to be Actor in a world where the certainties that underwrote John Wayne's actions are gone. Elvis seems to understand that what characterizes Actor is the will, that being Actor involves reclaiming what Nietzsche calls ‘the innocence of becoming’. But like the Lagos he inhabits, Elvis finds himself incapable of any creative act of will; instead succumbs to the nihilism that GraceLand depicts as characteristic of post-Biafra Nigeria.

In 1983, Elvis lives with his father and stepmother in Maroko, then one of Lagos's largest slums (it was bulldozed in 1990). Much of the story concerns his interactions with his father and three people he meets in Lagos: the Colonel, whose criminal ring employs Elvis; Redemption, Elvis's friend and cohort in crime; and the King of Beggars, whom Elvis befriends and who subsequently takes Elvis in when his life is endangered by the Colonel. Regularly interspersed with this story are flashbacks to Elvis's childhood in Afikpo beginning in 1972 and working their way forward until they catch up with the main narrative.