Australia has an established history of migration from the Middle East. In recent years, however, the emergence of international terrorism has defined those from that area as the new enemy; yet we do not fully understand the impact of this on the settlement experiences of migrants from that region. Given Australia’s migration pattern is dominated by skilled migration, this exploratory study sought to investigate how a small sample of self-selected skilled migrants from the Middle East experienced job seeking and settlement in Melbourne, Australia. Seven individuals participated in semi-structured interviews during July–August 2009. Thematic analysis revealed that participants had high, but ultimately unfulfilled, expectations for life and employment in Australia. Those immigrating with families experienced initial difficulties securing stable and suitable housing. The majority of participants struggled to find equivalent employment. This was seen to be influenced by their lack of both local qualifications and experience; differing cultural expectations about behaviour in job interviews was also an issue raised as influential. These challenges, combined with lack of government support, led to social isolation, psychological vulnerability and financial hardship.