Johnston's breakthrough novel, 1998's The Colony of Unrequited Dreams - shortlisted for both the Giller Prize and the Governor General's Award for fiction - was acclaimed for its historical portrayal of legendary Newfoundland politician Joey Smallwood.

It won the New York Public Libraries Prize for Best Novel and was chosen by the Los Angeles Times as one of the Ten Best Books of the year in 1999.

The novel was chosen for the 2003 edition of CBC Radio's Canada Reads competition, where it was championed by notable politician Justin Trudeau, and won the People's Choice Award.

Johnston's The Custodian of Paradise, published in 2006, told the story of Sheilagh Fielding, a fictional character originally introduced in Colony of Unrequited Dreams.

In 2002, Johnston published The Navigator of New York, a historical novel about the race by explorers to reach the North Pole; it was shortlisted for both the Giller Prize and the Governor General's Award for fiction.

His convocation address to the University of Alberta was subsequently published as "The Old Lost Land of Newfoundland: Family, Memory, Fiction and Myth" (2009, 47 pages) in the Henry Kreisel Lecture Series.