As some of the other answers already say, legendary cards will not automatically win a game. Yes, they're powerful, but very few of them will turn the tide instantly from one person to the other. Likely, the real issue is you are coming up against people who have better deck synergy than you do because they have many more cards in their library, as evidenced by their number of legendaries. This is the real blocking point for many new Hearthstone players.
To counter this lack in your own library, the number one thing you need to focus on is defeating the various solo adventures. Some of the best cards in the game come from there, like Loatheb or Kel'Thuzad, both legendary as are many of the other rewards. Until you can manage to increase the size of your library, you need to focus on building decks that don't require specific cards to perform well. For many people, this means Zoo warlock decks and basic mages. You need 0 cards outside of the basics to perform well as a mage because they get board clears, removals, etc all as part of their level up line. Warlocks often have a card advantage due to their hero power so they play well with lots of small minions that can zerg the other player if they don't get their board clears early on.
As was mentioned, 5 losses straight doesn't mean much when you're new. Its a fun game that becomes more fun when you can actually compete more fairly. Until then, focus on the weaknesses of the game, like the imbalance that the Mage class has, and go from there.
Also, play tavern brawl every single week. Your first win gets you a free card pack and you can complete quests there. And many weeks, you are playing with decks that are created randomly or given to you and don't require that you have the cards yourself. Brawls are a great way to learn the intricacies of the meta game, even though many of them heavy favor mages.