The analysis of dynamical complexity in nonlinear phenomena is an effective tool to quantify the level of their structural disorder. In particular, a mathematical model of tumor-immune interactions can provide insight into cancer biology. Here, we present and explore the aspects of dynamical complexity, exhibited by a time-delayed tumor-immune model that describes the proliferation and survival of tumor cells under immune surveillance, governed by activated immune-effector cells, host cells, and concentrated interleukin-2. We show that by employing bifurcation analyses in different parametric regimes and the 0-1 test for chaoticity, the onset of chaos in the system can be predicted and also manifested by the emergence of multi-periodicity. This is further verified by studying one- and two-parameter bifurcation diagrams for different dynamical regimes of the system. Furthermore, we quantify the asymptotic behavior of the system by means of weighted recurrence entropy. This helps us to identify a resemblance between its dynamics and emergence of complexity. We find that the complexity in the model might indicate the phenomena of long-term cancer relapse, which provides evidence that incorporating time-delay in the effect of interleukin in the tumor model enhances remarkably the dynamical complexity of the tumor-immune interplay.