Earliest possible winning turn in Hearthstone

A win on your first turn is possible if you play as a Druid against another Druid who plays Millhouse on their first turn.

In the video below, the opposing druid opens with an Innervate and summons Millhouse Manastorm. Millhouse's battlecry says: "Enemy spells cost (0) next turn." (Which means your spells cost (0) on your opening turn.)

Next, the player uses this opportunity play just shy of their entire deck and win. A pivotal card is Gadgetzan Auctioneer, which gives them a card every time they play a spell - giving them a virtually endless supply of 0-mana spells.

Source

I found a recent Reddit post of a turn 3 win as a mage (now known as Winner) versus a mage (unfortunately now known as Loser).

The winning mage went second, so got an extra card and coin.

Starting deck:

• Sorcerer's Apprentice (your spells cost 1 less)
• Mana Wyrm (whenever you cast a spell, gain 1 attack)
• Ice Lance
• Arcane Missiles
• Coin

The Sorcerer's Apprentice and the Mana Wyrm are the reason this turned out the way it did. But not to forget the nice amount of luck of drawing so many spells to begin with.

Turn 1:

• Winner draws Frost Bolt.
• Loser plays nothing.
• Winner uses Mana Wyrm (1 mana).

Turn 2:

• Winner draws Mirror Image.
• Loser pings Winner's Mana Wyrm (hits it for 1 damage).
• Winner uses Sorcerer's Apprentice (2 mana).
• Arcane Missles (0 mana) - 3 damage to hero - Mana Wyrm is at 2 attack.
• Coin (0 mana) - gains 1 mana back - Mana Wyrm is at 3 attack.
• Frost Bolt (1 mana) - 3 damage to hero - Mana Wyrm is at 4 attack.
• Ice Lance (0 mana) - 4 damage to hero - Mana Wyrm is at 5 attack.
• Mirror Image (0 mana) - Mana Wyrm is at 6 attack.
• Mana Wyrm attacks - 6 damage to hero.
• Loser takes: 3 + 3 + 4 + 6 = 16 damage and is left with 14 hp.

Turn 3:

• Winner draws Fireball.
• Loser plays Arcane Intellect.
• Winner uses Fireball (3 mana) - 6 damage to hero - Mana Wyrm is at 7 attack.
• Mana Wyrm attacks - 7 damage to hero.
• Sorcerer's Apprentice attacks - 3 damage to hero.
• Loser takes: 6 + 7 + 3 = 16 damage.
• Winner wins :)

This is without the Loser inflicting any damage on themselves. Obviously I am unsure if the other player had the means to kill the Mana Wyrm at any point, but I suspect they would've if they could.

This is just one example, and as the game progresses, Blizzard may re-balance certain cards making the above and other quick kills impossible.

But I hope that gives you an idea. As TZHX pointed out in the question comments, you can't rely on these strategies to win you games consistantly :)

Source

The turn 3 victory can also be completed easily with the Shaman with just 3-4 cards thus removing the need for lucky draws beyond the initial hand:

Turn 1 Dust Devil (3/1 windfury overload 2) + coin + Dust Devil
Turn 2 12 Damage (4 attacks)
Turn 3 Flametongue Totem (20 damage) or 2x rockbiter weapon (24 damage)

Note you have 1 spare crystal on turn 3 for 1 lightning bolt or earth shock to remove any taunts.

Note 2, you can subsitute a young dragonhawk for a second dust devil but you will need both the flametongue and rockbiter, or 2x rockbiter and a lightning bolt for the finishing blow.

Of course, this is highly susceptible to any form of removal, but a windfury shaman deck has enormous early+midgame damage output and is great for farming daily quests as its guarenteed to be a fast win or loss.