Objective Access to primary healthcare (PHC) services is key to improving health outcomes in rural areas. Unfortunately, little is known about which aspect of access is most important. The objective of this study was to determine the relative importance of different dimensions of access in the decisions of rural Australians to utilise PHC provided by general practitioners (GP). Methods Data were collected from residents of five communities located in ‘closely’ settled and ‘sparsely’ settled rural regions. A paired-comparison methodology was used to quantify the relative importance of availability, distance, affordability (cost) and acceptability (preference) in relation to respondents’ decisions to utilise a GP service for non-emergency care. Results Consumers reported that preference for a GP and GP availability are far more important than distance to and cost of the service when deciding to visit a GP for non-emergency care. Important differences in rankings emerged by geographic context, gender and age. Conclusions Understanding how different dimensions of access influence the utilisation of PHC services is critical in planning the provision of PHC services. This study reports how consumers ‘trade-off’ the different dimensions of access when accessing GP care in rural Australia. The results show that ensuring ‘good’ access requires that policymakers and planners should consider other dimensions of access to services besides geography. What is known about the topic? Research indicates that poorer ‘access’ to GPs, an impediment to seeking primary care at times of need, is the most important factor distinguishing rural from urban health service utilisation behaviour, which undoubtedly contributes to the poorer health outcomes characterising rural and remote populations. Much of the policy on access to date has focussed on increasing the number of GP located in rural and remote areas that are characterised by acute medical workforce shortages. What does this paper add? This study provides empirical data to show how different dimensions of access influence rural Australians’ decisions to utilise a GP service. Overall, rural Australians rank preference for a GP as the most important factor in their decision to visit a doctor for a non-emergency consultation. Important differences in rankings emerged by geographic context, gender and age. Distance to a GP service ranks consistently as the third most important access factor and cost is rated the least important aspect of access. What are the implications for practitioners? Although current rural health policies and incentives should continue to target the need to increase the availability of GP in non-metropolitan areas, this alone may not be sufficient to improve GP service utilisation. Other dimensions of access, particularly consumer preference, which are amenable to interventions both nationally and locally, are equally important.