Embodiments of the present disclosure disclose a method and apparatus for searching a video segment, a device and a medium, and relate to the field of video data search. The method includes: sampling video frames from a target video and videos to be searched in a video library, and extracting features from the sampled frames; matching the target video and the videos to be searched according to the extracted features to determine a candidate video to be searched that matches the target video; determining at least one candidate video segment from the determined candidate video, and calculating a degree of matching between the target video and each candidate video segment based on the extracted features of each sampled frame; and determining a video segment matching the target video in the videos to be searched according to the calculated degree of matching between the target video and each candidate video segment.