Considering the keyword search on the Web, it is often difficult for the users to specify queries that precisely describe what they need. In fact, such kind of queries can be very complex. It is therefore unrealistic for the search engines on the Web to demand precise queries directly from the users. In this paper, we propose a new method for query refinement that allows users to specify simple queries and then repeatedly refines the queries. Our method takes advantage of the historical information (user feedbacks and query term associations) to refine queries. For performance evaluation, we consider various methods for query refinement and implement these methods into a search engine on the Web to make a series of experiments on real data/users. The results show that the historical information is very helpful for effective search on the Web.