(1) Background: The emergence of autonomous vehicles (AVs) is likely to have substantial implications for walking behaviours due to the availability of new transport options and altered physical environments within cities. The aim of this exploratory study was to identify AV-related factors that could affect walking at the population level and strategies to ameliorate any negative effects. (2) Methods: A total of 46 Australian expert stakeholders were interviewed about their perceptions of the potential impacts of AVs on walking behaviours. The interviewees represented government departments (state and federal), non-government organisations (NGOs), private sector companies, peak bodies, and academia. (3) Results: Interviewees expected AVs to have different effects on individuals’ ability and motivation to engage in planned versus incidental walking. While those with innate motivation to walk as a form of exercise or leisure may experience enhanced participation opportunities, it appears that incidental walking could be adversely impacted through the availability of convenient AV door-to-door transport options and automated home delivery services that reduce walking related to commuting and shopping. (4) Conclusions: Proactive policy actions are needed to optimize the potential positive impacts of AVs on walking and circumvent the potential negative impacts on valuable incidental walking that constitutes a key component of many people’s total physical activity.