This book constitutes the thoroughly refereed post-conference proceedings of the 4th International Workshop on New Frontiers in Mining Complex Patterns, NFMCP 2015, held in conjunction with ECML-PKDD 2015 in Porto, Portugal, in September 2015. The 15 revised full papers presented together with one invited talk were carefully reviewed and selected from 19 submissions. They illustrate advanced data mining techniques which preserve the informative richness of complex data and allow for efficient and effective identification of complex information units present in such data. The papers are organized in the following sections: data stream mining, classification, mining complex data, and sequences.