The study explored whether career mentoring moderates the direct and indirect relationship between career-related anxieties and job search outcomes through job search strategies. Three-wave panel data were collected from three hundred and fifteen (315) unemployed graduates in Southeastern Nigeria. Results from Structural Equation Modelling (SEM) provided support for the direct, indirect, and moderation hypotheses. Specifically, the results showed that job search anxiety was negatively related to job search outcomes. Job search behavior and systemacity in job search significantly mediated the relationship between future career anxiety and job search outcomes. We recommend that job search behavior, job search systematicity, and career mentoring are important in finding jobs. We discussed limitations and future research, as well as recommendations for career counseling practice and research.