The purpose of this paper is to investigate the use of discourse markers that Yemeni EFL learners use in their composition writings. The research questions addressed in this paper are (1) what are the DMs that are frequently used by Yemeni EFL learners? and (2) is there a direct relationship between the use of such markers and the writing quality of the learners in question? The 50 essays written by the study sample were analyzed following Fraser's (1999) taxonomy. The findings of the study reveal that the most frequently used discourse markers are the elaborative ones, followed by the inferential, contrastive, causative and topic relating markers. It is also shown that there is no strong positive correlation between learners' total number of discourse markers used and the writing quality of the participants. There is, however, a positive correlation between the topic relating markers and the writing quality of the learners. The paper concludes with some recommendations and suggestions that should inform EFL writing instruction in this part of the world and in other similar contexts.