This book constitutes the thoroughly refereed post-conference proceedings of the Second International Workshop on New Frontiers in Mining Complex Patterns, NFMCP 2013, held in conjunction with ECML/PKDD 2013 in Prague, Czech Republic, in September 2013. The 16 revised full papers were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on data streams and time series analysis, classification, clustering and pattern discovery, graphs, networks and relational data, machine learning and music data.