This is the first of a four-part guide to get into pet battling.
The other three parts are:
Part 2: Guide: After your first Level 25
Part 3: Guide: Your early pet roster
Part 4: Guide: Your First Safaris
When pet battlers talk about pets and strategies, we always assume we mean pets that are at Level 25, and Blue (Rare) quality.
Getting at least one pet to Level 25 is a Big Deal at the start of pet battling. It means you can use that Level 25 to demolish lower level battles, and help capture and level more pets. It also means you can buy and learn (uncage) more Level 25 pets from other players or the Auction House.
As of March 2023, Patch 10.0.5, there are five basic approaches to getting your first pet to 25, using two different mechanisms.
The two mechanisms are:
- Gain XP by battling. In every pet battle, a certain amount of XP can be awarded to any sub-25 pet you use on your team. The amount of XP varies depending on the level of your pets vs the level of the opposition pets, plus a huge XP bonus for defeating tamers.
- Gain XP by using Stones. There are various Battle-Training Stones available. Some [Yellow] give 2,000 XP, at least one level for a level 24, and more levels for lower pets, one [Green] gives 10,000 XP, and one [Purple] gives 25 levels. Summon your pet, target it, and right-click the Stone to apply the level boost.
There is also a Blue stone Marked Flawless Battle-Stone that does not increase a pet’s level, but does increase its Quality to Rare (Blue).
Stones are easy to come by once you have a good roster of 25s and have the world quests on farm, but they are scarce before that.
Approach 1: Gain XP by battling through the Tamers
This is the intended method, and best for experience and learning, but slower than the others. The basic idea is to collect pets that you battle around the zones, capturing good-looking recruits as new pets, and defeating the Tamers in order.
The Tamers can be found all around the continents, and have pets at various levels as you ascend through the chain.
As Horde, you should follow Taming Kalimdor to start.
Alliance characters do Taming Eastern Kingdoms instead of Kalimdor, which sometimes causes problems for people trying to do pets on characters from both factions. If you have characters on both factions, it’s safest to do either one, but not mix them until you have completed one.
Once out of the original continents, both factions then do Taming Outland, Taming Northrend, Taming Cataclysm, Taming Pandaria, in that order.
As you do that, you will naturally level your original pets and the ones you tamed along the way.
You will learn about families, and what is strong against what.
Importantly, along the way, you will complete all the Taming achievements up to and including Pandaria, which open up all those quests as dailies, and you can use those to level more pets later. It also brings you within one battle of your Safari Hat.
Approach 2: Gain XP by battling with skips
This video shows the fastest method for getting one level 25 pet by battling with skips
It works. I’ve tried it myself. It takes maybe 2 or 3 hours, and you will likely fail battles when trying to capture something a couple of times along the way, but it works.
You will end up with a pet at 25, but it will be some random wild pet, probably a Critter, that you capture in Pandaria. However, of course, once you have any Level 25 pet, you can buy and learn any other Level 25 cageable pet.
In this method, you take maximum advantage of Family strength types to capture pets of much higher level, and thus skip rungs on the ladder. Instead of capturing a Level 10 pet with Level 8 pets, you use Level 5-ish pets to capture Level 14 pets, then use those 14 pets to capture Level 23-25 pets.
Basically, pick up a couple of Level 4-6 Shore Crabs on the coast in Azshara or Westfall .
Fly off to Badlands where you can use them to beat Level 14 critters.
When you have captured a couple of Level 14-16 Strand Crabs in Swamp of Sorrows, fly to Valley of the Four Winds, where you can beat the Critters and capture a 23-25 Critter.
Now go to the Briny Muck in Dread Wastes and serve your inevitable hour or two looking for the Blue P/P Emperor Crab you’ll have to catch anyway someday, so you might as well get some XP out of the search.
Approach 3: Earn a Purple Level 25 Boost Stone with your Garrison
You can buy your first 25 by getting your Draenor Garrison to Level 3. Then a quest for Horde or Alliance pops up that rewards you an Ultimate Battle-Training Stone, that levels one pet to 25 instantly.
This is great if you have a Level 3 Garrison. Getting your Garrison to Level 2 is easy enough, but Level 3 requires 2000 Garrison Resources and 5,000 Gold, so that may be a consideration. If you have lots of Gold, Garrison Resources can be bought at the Auction House in the form of Huge Ogre Cache.
Approach 4: Earn a Purple Level 25 Boost Stone with World Quests
Battle for Azeroth and Shadowlands and Dragonflight Pet World Quests often reward between 14 and 20 Polished Pet Charms each.
With 35 Polished Pet Charms you can buy one Ultimate Battle-Training Stone, that levels one pet to 25 instantly, from pet vendors in Legion Dalaran, BfA or Oribos.
So you need to beat 2 or at most 3 BfA or Shadowlands or Dragonflight World Quests that reward Charms.
The good news is that these battles scale to the level of your highest pet, so if you tackle them with all Level 1 pets, you will only have to beat the tamers using Level 1 pets, and this is actually a lot easier than beating them with Level 25s. There are no guides to completing these battles with Level 1s, but they are not terribly hard. Just use counters as much as you can - Undead against Humanoids, Dragons angainst Flyers, Elementals against Mechanicals, and so on.
Approach 5: The Dragonflight Lubbins quesline
In Dragonflight, Blizzard introduced a way for a Level 70 to get three 25 pets quickly through a short quest chain. It is available only once per account, so you can’t repeat it on multiple alts.
The Quest Oh Where, Oh Where Can He Be begins a sequence that leaves you with Lubbins (a Dragonkin), a Shyfly (a Flier), and Mister Toots (a Beast). These are all respectable but not top-tier pets. Along the way, you will pick up two Purple stones, that will boost a pet to level 25, and a Blue Stone, that will make a pet Rare. The devs obviously intend that you use the Stones on these pets, but that is not required. You could use them on some of the Most Used pets, if you have Level 1s of them, or the pets mentioned below in the Postscript.
Postscript: Which pet to Boost
If you earned a Purple Stone to boost one pet to 25, which should you pick?
Well, any pet is good, since you can then buy more Level 25 pets and learn them, but my personal choice would be Anubisath Idol, Teroclaw Hatchling, which is dirt-cheap on the AH, or Void-Scarred Anubisathl, which is very similar to the venerable Idol, and may actually be a bit better for a new player.
There are many other possible good beginning tradeable 25s, including Chrominius and Mechanical Pandaren Dragonling, that are much used in many strategies, but that discussion goes beyond the scope, and I’m getting tired of typing. 
Whatever you chose to boost or buy, congratulations on your first Level 25, and don’t spend all your gold on the first AH pets you see! 