In recent years, there have been various systems developed to encourage people to engage in walking related activities. In this paper, we propose one such system and outline the concept for how a smart walking navigation system could be developed based on the notion of perceived exertion. Our system utilizes information about the geographical characteristics of the route along with data from social media to recommend a route for the user. In addition, we describe the results of 3 feasibility experiments carried out on the recommended routes by subjects studies, which overall support our proposed concept.