This book constitutes the refereed proceedings of the 4th International Conference on Theory and Practice of Natural Computing, TPNC 2015, held in Mieres, Spain, in December 2015. The 12 revised full papers presented together with 20 invited talks in this book were carefully reviewed and selected from 30 submissions. The scope of TPNC is rather broad, containing topics of either theoretical, experimental or applied interest such as soft computing, computing architectures, and formal models.