The increasing use of multimedia streams nowadays necessitates the development of efficient and effective methodologies and systems for manipulating databases storing these streams. These systems have various areas of application such as video-on-demand and digital libraries. The importance of video content-based retrieval (CBR) systems motivates us to explain their basic components in this chapter and shed light on their underlying working principles. In general, a content-based retrieval system of video data consists of the following four stages: (1) Video Shot Boundary Detection, (2) Key Frames (KFs) selection, (3) features extraction (from selected KFs), and (4) retrieval stage (where similarity matching operations are performed). Each one of the above stages will be reviewed and expounded based on our experience in building a Video Content-based Retrieval (VCR) system that has been fully implemented from scratch in JAVA Language (2002). Moreover, current research directions and outstanding problems will be discussed for each stage in the context of our VCR system.