This exploratory practice study addresses the puzzle of EFL writing anxiety experienced by pre-service teachers. To decipher the puzzle, probe its likely causes, and propose solutions, we conducted an exploratory study with a group of 37 first-year, preservice teachers at the Higher Institute of Human Sciences of Medenine (HIHSM), Tunisia, using a task-based language teaching (TBLT) approach as a potential remedy for the puzzle. Data were gathered via (a) a student needs analysis on the challenges encountered while doing writing assignments, (b) our reflections on the design and implementation of a TBLT lesson plan, (c) a student satisfaction survey on the TBLT experiment, and (d) students' writing assignments. Our findings show that a TBLT-inspired writing sequence boosted students' enthusiasm, motivation and self-confidence, lessened their anxiety, and improved their writing quality. The implementation of TBLT was, however, not without challenges.