Complex reasoning in Temporal Knowledge Graph Question Answering (TKGQA), which requires both Knowledge Graph (KG) navigation and temporal computation, has received limited attention because current datasets often have limited coverage of multi-hop retrieval and computations. To address this gap, we propose a taxonomy of complex reasoning in TKGQA, which consists of two dimensions: structural complexity and computational complexity. Guided by this taxonomy, we construct CR-TKGQA, a new TKGQA dataset for Complex Reasoning. CR-TKGQA consists of more than 30,000 natural language questions, each paired with an executable SPARQL query on Wikidata. Its intent-driven construction ensures broad coverage across both complexity dimensions, achieved by first seeding computational complexity from human intent and then automatically augmenting structural complexity. Experiments show CR-TKGQA poses challenges to current baselines.