Objective: This study examined whether attributes of pedestrian environments moderate the relationships between access to public open spaces (POS) and adults' recreational walking. Methods: Data were collected from participants of the North West Adelaide Health Study in 2007. Recreational walking was determined using self-reported walking frequency. Measures of POS access (presence, count, and distance to the nearest POS) were assessed using a Geographic Information System. Pedestrian environmental attributes included aesthetics, walking infrastructure, barrier/traffic, crime concern, intersection density, and access to walking trails. Regression analyses examined whether associations between POS access and recreational walking were moderated by pedestrian environmental attributes. Results: The sample included 1574 participants (45% men, mean age: 55). POS access measures were not associated with recreational walking. However, aesthetics, walking infrastructure, and access to walking trail were found to moderate the POS-walking relationships. The presence of POS was associated with walking among participants with aesthetically pleasing pedestrian environments. Counter-intuitively, better access to POS was associated with recreational walking for those with poorer walking infrastructure or no access to walking trails. Conclusion: Local pedestrian environments moderate the relationships between access to POS and recreational walking. Our findings suggest the presence of complex relationships between POS availability and pedestrian environments.