This book constitutes the thoroughly refereed conference proceedings of the First International Workshop on New Frontiers in Mining Complex Patterns, NFMCP 2012, held in conjunction with ECML/PKDD 2012, in Bristol, UK, in September 2012. The 15 revised full papers were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on mining rich (relational) datasets, mining complex patterns from miscellaneous data, mining complex patterns from trajectory and sequence data, and mining complex patterns from graphs and networks.