The first music video-like would be The Little Lost Child in 1894 (!!). This is considered more like the first illustrated song. Using a magic lantern, a series of still images were projected on a screen simultaneous to live performances.
The first music video as we know it today, was Tony Bennett's "Stranger in Paradise"(1953) (cannot find it online).
The next music video was Elvis's "Jailhouse Rock" (1957)