Due to the unstable network environment and fake quality propagation, the published service quality by service providers is not always trustable. Therefore, it becomes a necessity to evaluate the real quality of a web service, based on the service's historical records. However, for a web service, its multiple historical records often vary in execution context (e.g., execution time, user input, user location, etc.), which brings a great challenge to discriminate and rank all the historical records of an identical web service. Besides, for all the candidate web services, their historical record number (i.e., the times that a service was invoked) may be different, which may also affect the user's final service selection decision. In view of these challenges, we put forward a novel service selection approach CSS_HR (Context-aware Service Selection based on Historical Records). In CSS_HR, we first quantify the weight of each historical record, based on its context similarity with current user's service invocation; and afterwards, we quantify the weight of each candidate web service based on its historical record number; finally, with the derived weights of historical records and weights of candidate services, we evaluate all the candidate services and select a quality-optimal one. Through a set of experiments, we validate the feasibility of our proposal.