Physical systems with co-existence and interplay of processes featuring distinct spatio-temporal scales are found in various research areas ranging from studies of brain activity to astrophysics. The complexity of such systems makes their theoretical and experimental analysis technically and conceptually challenging. Here, we discovered that while radiation of partially mode-locked fibre lasers is stochastic and intermittent on a short time scale, it exhibits non-trivial periodicity and long-scale correlations over slow evolution from one round-trip to another. A new technique for evolution mapping of intensity autocorrelation function has enabled us to reveal a variety of localized spatio-temporal structures and to experimentally study their symbiotic co-existence with stochastic radiation. Real-time characterization of dynamical spatio-temporal regimes of laser operation is set to bring new insights into rich underlying nonlinear physics of practical active- and passive-cavity photonic systems.