Gainful employment is critical to successful reentry into society for the formerly incarcerated. However, stigmatization based on criminal history makes labor market success difficult for these individuals. Empirical analysis of employment outcomes for Americans with criminal histories focuses largely on the perspectives of employers and lacks exploration into the choices, motivations, and agency of those facing criminal stigmatization. In this dissertation, I use a mixed-methods approach to investigate how criminal stigmatization is related to job search strategies and employment outcomes. In chapter 1, I provide a background and literature review of the body of work that forms the basis for my questions. In chapter 2, I investigate whether there are differences in the job search strategies used by the formerly incarcerated compared to those never incarcerated in the NLSY97, a nationally representative longitudinal data set. I then explore whether an incarceration spell changes the job search strategies of the formerly incarcerated by comparing their pre-incarceration job search strategies to their post-incarceration job search strategies. Finally, still using the NLSY97 data, I examine how specific job search strategies are related to employment outcomes for the formerly incarcerated compared to those never incarcerated. Chapters 3 and 4, use qualitative data I collected through interviews with formerly incarcerated individuals to explore the role of stigmatization during the job search for the formerly incarcerated. Specifically, in Chapter 3, I dig deeper into what the "other" strategies formerly incarcerated job seekers might be using to search for employment. I explore the ways that they network, despite the limitations highlighted by previous literature. I explore their use of reentry programs and extend the discussion of the selection process highlighted in previous research. There is evidence that, for the formerly incarcerated who participate in reentry programs, they may already have skills and knowledge that make them more likely to be successful in the job market. In chapter 4, I explore the role of stigma more closely, operationalizing stigmatization as the decision of the formerly incarcerated to check the box acknowledging their criminal record on job applications, as opposed to the act of rejecting the stigma by not doing so. I explore how the formerly incarcerated legitimize or delegitimize the stigma associated with a criminal background and how this relates to the strategies they use to find a job. I describe the ways those in my sample enact their agency to signal their skills and worthiness of hire to employers. I find considerable evidence that the formerly incarcerated enact similar strategies as those never incarcerated, but that these strategies are coupled with a network of support that contributes to successful employment outcomes. I contend that sponsorship is critical for the formerly incarcerated to successfully reenter society and become productive members. In chapter 5, I conclude with a discussion of the contribution of this research, implications and applications of my findings for the formerly incarcerated in the labor market, and directions for future research.