Relevance is one of the most fundamental concepts in information science. However, among the large body of relevance literature, very little of the research studied users’ relevance judgments when concerning video. The pilot study described in this paper conducted exploratory work in this direction. The time-line interview method proposed by Dervin (1992) was applied in the study due to its exploratory and descriptive nature. Four subjects were interviewed in early 2003, including a professor in communication studies, an art professor, a news video librarian and a video editor. Using inductive content analysis methods, three categories of relevance judgment criteria were summarized: textual criteria (e.g., topicality, recency, and nationality), visual criteria (e.g., cinematography, objects/events, and style) and implicit criteria (e.g., interest, familiarity, and appropriateness). Topicality was still considered the most important criteria for video relevance judgments, however, users also liked to see visual surrogates, especially those surrogates that contained motion. A more formal study is planned, and we expect that the results will not only enrich the relevance literature but also have implications for current video indexing and retrieval research.