This paper presents an approach to investigating the possibility for constructing an automatic and scalable thesaurus based on Web users’ vocabularies with search interests. The proposed approach mainly includes two techniques, namely, relevant term extraction and concept clustering. The former combines query-session-based and text-based methods to extract relevant terms for a given search term; and the latter organizes these relevant terms into concept classes based on the search results from search engines. Some initial experiments have been conducted to test feasibility of the proposed approach to organizing Web users’ vocabularies. The obtained results show that relevant terms could be extracted efficiently and concept classes be more well organized. The approach has a great potential to benefit the automatic construction of a large scale thesaurus for future Web IR applications.