This article examines the role of student job search strategies that differ in goal-directedness (focused, exploratory, and haphazard) in achieving successful university-to-work transitions (i.e., employment in jobs with high skill use/development and qualification-job match). The relationship between job search and employment outcomes is considered in two labor market contexts--high or low ambiguity--which are represented by the comparison between arts, humanities, and social sciences (AHSS) and science, technology, engineering, and mathematics (STEM) graduates, respectively. Using two-wave survey data, we find that job search strategies during university do not explain, yet differentially impact, successful outcomes one year after graduation. Fully exploring opportunities was particularly beneficial for STEM graduates (low ambiguity context) and more focused job search was beneficial for AHSS graduates (high ambiguity context). Paradoxically, findings both question and reinforce the efficacy of career agency for overcoming barriers to labor market entry, depending on the job search context. The study contributes to the agency and context debates relevant for school-to-work transitions.