Conversational Intelligent Tutoring Systems (CITS) represent a convergence of artificial intelligence, learning sciences, and human-computer interaction, aiming to provide the adaptive and dialogic learning as expert teachers. In the past decades, the advancement of machine learning and natural language processing reshaped CITS’s design, implementation, and evaluation. In this survey, we analyze the evolution of computational paradigms in shifting pedagogical affordances, interaction styles, and methodological development. We frame CITS not merely as dialogue systems, but as proactive agents that reason about learner cognition, affect, and context while enacting pedagogical strategies grounded in educational theories. From domains, populations, and instructional goals, we identify key components, evaluation approaches, and unresolved challenges. Our paper highlights the promise and limitations of conversational tutoring in the generative AI era, offering a foundation for future research that seeks to maximize their pedagogical value.