Tindall [Int J Syst Evol Microbiol 58 (2008), 1979–1986] claimed that the International Code of Nomenclature of Prokaryotes (the Code) creates a paradox in the application of the term ‘legitimate’ in relation to valid publication, that the term is dispensable and that the paradox would be resolved by revising the Code to avoid its use. Although it is not clearly explained in the Code, the concept of legitimacy is central to the proposal of names. Discarding the concept would fundamentally alter the conceptual structure of the Code and obscure significant distinctions in formal nomenclature. The text of the Code itself is not clear and a careful reading suggests that it would be enhanced by a critical overview involving textual revision and restructuring of some sections. The Judicial Commission is asked not to accept Tindall's suggested revision and it is proposed that the Editorial Board of the International Committee on Systematics of Prokaryotes re-examine the Code from first principles and make such revisions as will avoid in future the confusion, ambiguities and uncertainties indicated here.