Theoretically, the earliest it can occur (for Black) is on move 4, as White needs 4 moves to castle. However my attempts to construct a game where this happens (eg 1.e4 e6 2.Bc4 Bd6 3.Ne2 Nf6 4. O-O Bxh2+) just leads to White getting a better position, as White can defend by bringing the king to g3.
Our searching turned up lots of games where Bxh2+ was not a real sacrifice, as White has a bishop on g5. There were also games where Black sacrificed and lost, so we discarded those games as well. In the end we found one game where Black sac'ed on move 6, but that was about it. So the following game goes very close to equalling a record, missing out by 1 move.
Jochimsen,Erik - Litchfield,Fred [D00]
ANU Spring Swiss, 28.10.2015