There is a well established theory that links semi-Markov chains having Mittag-Leffler waiting times to time-fractional equations. We here go beyond the semi-Markov setting, by defining some non-Markovian chains whose waiting times, although marginally Mittag-Leffler, are assumed to be stochastically dependent. This creates a long memory tail in the evolution, unlike what happens for semi-Markov processes. As a special case of our chains, we study a particular counting process which extends the well-known fractional Poisson process, the last one having independent, Mittag-Leffler waiting times.