Over 750000 refugees have resettled in Australia since 1945. Despite complex health needs related to prior traumatic experiences and the challenges of resettlement in a foreign country, refugees experience poor access to primary care. Health and settlement service providers describe numerous cultural, communication, financial and health literacy barriers. This study aimed to investigate the acceptability of general practitioner (GP) services and understand what aspects of acceptability are relevant for Afghan refugees in south-eastern Melbourne. Semi-structured interviews were conducted with two Afghan community leaders and 16 Dari- or English-speaking Afghan refugees who accessed GP services. Two distinct narratives emerged - those of recently arrived refugees and established refugees (living in Australia for 3 years or longer). Transecting these narratives, participants indicated the importance of: (1) a preference for detailed clinical assessments, diagnostic investigations and the provision of prescriptions at the first consultation; (2) ‘refugee-friendly’ staff; and (3) integrated, ‘one-stop-shop’ GP clinic features. The value of acceptable personal characteristics evolved over time - GP acceptability was less a consideration for recently arrived, compared with more, established refugees. The findings reinforce the importance of tailoring healthcare delivery to the evolving needs and healthcare expectations of newly arrived and established refugees respectively.