Labour market entry poses enormous challenges for recently arrived refugees, ranging from language barriers, devaluation of human capital, unfamiliarity with customs of the job search process to outright discrimination. How can refugees overcome these challenges and quickly enter gainful employment? In this paper, we draw on interviews with 26 male and female refugees from Syria, Afghanistan, Iraq and Iran, conducted in 2017 and 2018, who came to Austria in 2015 and 2014 and who have successfully entered employment. We depict refugees’ own perspectives on and strategies for fast job entry and integration. Personal agency and a proactive approach of seeking and seizing opportunities are key for overcoming initial barriers and entering upon positive integration pathways. At the same time, refugees’ personal agency is essential for establishing social ties to the host society, which also play a crucial role in early labour market integration. Finally, institutions of the Austrian labour market (the ‘apprenticeship’-system) interact with refugees’ agency in most intricate ways, both setting up nearly insurmountable barriers but also providing specific opportunities for refugees.