Methods, systems, and media for synchronizing video streams are provided. In some embodiments, the method comprises: identifying a target video stream and a reference video stream, wherein the target video stream and the reference video stream are two different broadcasts of a program; generating, for the target video stream, a sequence of fingerprints; determining a time shift at which the sequence of fingerprints appears within the reference video stream; determining whether the target video stream is synchronized with the reference video stream by determining whether the time shift exceeds a predetermined threshold; and, in response to determining that the target video stream is not synchronized with the reference video stream, causing an electronic programming guide that includes an indication of the target video stream to be modified based on the time shift.