In this paper, we propose CoDy, a paradoxical explanation method that provides explanations for individual instances independently of the model, to address the explainability problem of Temporal Graph Neural Networks (TGNNs), which are widely used to model dynamic systems where relations and features change over time. CoDy efficiently explores a vast search space of explainable subgraphs by exploiting spatial, temporal, and local event influence information using a search algorithm that combines Monte Carlo Tree Search and heuristic selection policies. Experimental results show that CoDy improves the AUFSC+ metric by 16% over state-of-the-art baseline models.