This book constitutes the thoroughly refereed post-proceedings of the 4th International Workshop on Formal Approaches to Software Testing, FATES 2004, held in Linz, Austria in September 2004. The 14 revised full papers presented were carefully selected during two rounds of reviewing and improvement; they are organized in topical sections on symbolic test generation, testing non-functional properties, test development with model checking techniques, and test optimization.