This short story collection was first published by Canongate in 2000. It was republished in a different edition by Canongate in 2006. The editions differed in their arrangement of the six stories featuring the Scottish pensioner Gordon, who first appeared in the story Armed Company Director in the 1992 collection Last Orders. In the earlier edition of The Museum of Doubt, the stories were spaced throughout the book. In the 2006 edition, the six stories were published as a novella at the end of the book under the collective title The Club of Men.

The stories, as reordered in the 2006 edition, are:

1. The Museum of Doubt

2. Bonny Boat Speed

3. The Very Love There Was

4. The Queen of Ukraine

5. Smoked

6. Management Secrets of the Nazi Generals

7. Class Action

8. The Return of the Godlike Narrator

The Club of Men:

i. These Lovers

ii. Pure

iii. And the Days Grow Shorter

iv. The Club of Men

v. Waterland

vi. Northern Soul