You have to finish the New Player experience if you start from a new account (reach rank 25, or skip the new player ranks to go directly to 25). If you are a returning player, I believe there is a quest or two, once done you go back to the screen and choose a deck. However:
So if you tried that yesterday, maybe try again today?
More details on the free deck:
https://us.forums.blizzard.com/en/hearthstone/t/a-few-notes-on-the-returning-player-experience/27240