We present a methodology for the non-linear analysis of long-term ecological time series. Using a time-delay embedding procedure, we investigated the complexity of 1-dimensional signals and compared their structure to their stochastic counterparts. Recurrence-based statistics and surrogate testing were used for this purpose. The method was first tested on elementary models for illustrative purposes and its potentialities and limits reviewed. We then investigated the time structure of 6 Mediterranean bluefin tuna trap catches known to display long-term fluctuations. These time series showed significantly more determinism than linear stochastic processes, displaying more recurring patterns/states than stochastic surrogates. The short term structure of these series also showed a direct and delayed negative feedback in their rate of increase. These results were homogeneous over all studied time series. An interaction between climate forcing and the life history traits of bluefin tuna was postulated to explain the first result, while the density-dependent pattern may be explained either by density-dependence processes during early stages, or by non-successive (non-yearly) spawning events in the Mediterranean.