This study aims to investigate performances and strategies of EFL graduate students in terms of language proficiency, language background and type of writing task. The participants were 12 graduate students pursuing their doctoral studies in ELT at a Turkish university. A chosen text was used for data collection and the students' paraphrased texts were analyzed employing Keck's (2006) the taxonomy of paraphrase types and 'a paraphrase found form' developed by the researcher in terms of lexical and structural changes. The results of the study revealed that graduate students had challenges in appropriate implementation of paraphrasing in their task. While they generated frequently moderate level of paraphrases, the strategies they often used were synonym substitution as well as copying strings of words from source. Additionally, deviated meaning was designated as a new paraphrase type in the taxonomy of paraphrase. These findings suggest that students need an explicit paraphrasing instruction supported by good and bad paraphrase examples and more practice to learn how to paraphrase appropriately.