In this paper, we present the Enhanced Learning Based Random Walk (ELBRW) recommender system for Places of Interest (POI), which leverages contextual information for providing more relevant POI recommendations. The ELBRW considers a model of contextual factors namely POI crowdedness based on a discrete-time Markov chain and combines user interests and "mobility homophily" for POI recommendation in Location- Based Social Networks (LBSNs). By comparing it to the Learning Based Random Walk (LBRW), a context- free recommender system, the performed experiments using LBSNs data provide promising results in terms of POI recommendation quality.