To examine associations between perceived destination accessibility within different distances from home and self-reported overall amounts of walking for different purposes among older adults (aged ≥ 65 years) in Brisbane, Australia (N = 793) and Hong Kong, China (N = 484). Perceived neighborhood destination accessibility types were derived from latent class analysis using comparable measures of perceived distance to 12 destinations from epidemiological studies in the two cities. Associations of perceived destination accessibility with measures of within-neighborhood walking were also estimated in Hong Kong participants. Better perceived destination accessibility was positively associated with the likelihood of walking in Brisbane participants only. Perceived destination accessibility within a short distance from home (5-min walk) was negatively related to the amount of within-neighborhood walking for transport in Hong Kong residents who walked. Our findings suggest that providing moderate-to-high, but not extreme, levels of destination accessibility may be optimal for the promotion of walking in older community dwellers.