Aspects of the subject matter described herein relate to searching files. In aspects, a search engine is able to search not only the current files but also is able to search for deleted and previous versions of files that satisfy queries. The search engine may maintain an index that facilitates searches. In addition, the search engine may also determine not only that a file satisfies a query but what version(s) of the file satisfies the query.