This volume contains the joint proceedings of the 9th International Conference on Relational Methods in Computer Science (RelMiCS-9) and the 4th International Workshop on Applications of Kleene Algebra (AKA'06). The joint event was hosted by the School of Computer Science at the University of Manchester, UK, from August 29 to September 2, 2006. RelMiCS/AKA is the main forum for the relational calculus as a conceptual and methodological tool and for topics related to Kleene algebras. Within this general theme, the conference series is devoted to the theory of relation algebras, Kleene algebras and related formalisms as well as to their diverse applications in software engineering, data bases and artificial intelligence. This year, special focus was on formal methods, logics of programs and links with neighbouring disciplines. This diversity is reflected by the contributions to this volume.