Sustained emerging spatio-temporal co-occurrence patterns (SECOPs) represent subsets of object-types that are increasingly located together in space and time. Discovering SECOPs is important due to many applications, e.g., predicting emerging infectious diseases, predicting defensive and offensive intent from troop movement patterns, and novel predator-prey interactions. However, mining SECOPs is computationally very expensive because the interest measures are computationally complex, datasets are larger due to the archival history, and the set of candidate patterns is exponential in the number of object-types. We propose a monotonic interest measure for mining SECOPs and a novel SECOP mining algorithm. Analytical and experimental results show that the proposed algorithm is correct, complete, and computationally faster than related approaches. Results also show the proposed algorithm is computationally more efficient than na?ve alternatives.