The present invention is directed to a search engine for a video recorder. One embodiment of the present invention operates in an environment that includes one or more set-top boxes connected to or integrated within one or more output devices. The set-top boxes are used to transfer shows from a broadcast input source to one or more types of storage devices and to play back the shows from the storage devices to the output devices, either in a delayed-live fashion or at a later time of the user's choosing. The set-top box displays a graphical user interface (GUI), which gives the user the ability to watch and/or record timeslot based programming, to order on-demand programming, and to playback previously recorded shows that reside on a local or remote storage device. A search engine is added to the GUI that lets the search for shows and receive results in an enhanced manner.