The two-volume set LNCS 9134 and LNCS 9135 constitutes the refereed proceedings of the 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, held in Kyoto, Japan, in July 2015. The 143 revised full papers presented were carefully reviewed and selected from 507 submissions. The papers are organized in the following three tracks: algorithms, complexity, and games; logic, semantics, automata and theory of programming; and foundations of networked computation: models, algorithms and information management.