Constitutes the refereed proceedings of the 15th International Symposium Fundamentals of Computation Theory, FCT 2005, held in Lubeck, Germany in August 2005. The papers are organized in topical sections on circuits, automata, complexity, approximability, computational and structural complexity, graphs and complexity, and more.