Patch 7.2 brought one of the most anticipated features in the pet battling world: a new pet battle dungeon!

To enter the dungeon you only need one level 25 pet in your collection (although it is recommended to have a few more ^^). Head over to Dalaran above the Broken Isles and visit the pet shop. Either Serr'ah or Lio the Lioness will offer you a breadcrumb quest to fly all the way over to the Wailing Caverns in the Barrens.
When you arrive, visit Muyani on top of the entrance and you will be offered the quest Wailing Critters. Muyani will also start the scenario for you.

Inside the dungeon, you will have to beat six waves of enemy pets. In your very first run, you can heal your pets in between each fight. This is the normal mode.
In the respective section here (green skull) you will find some strategies that work well. While having more pets is recommended to be done faster, most of the individual combinations will even work for the whole dungeon (with the help of a lot of healing).
Beating the dungeon on normal mode will reward you with one Ultimate Battle Training Stone.

It also unlocks the Challenge Mode, during which you cannot heal or revive your pets, much like the Celestial Tournament. If you also beat this additional challenge, you get an achievement and two rewards, the pet Son of Skum and a new satchel, the Damp Pet Supplies which has a chance for one of these:

Young Venomfang
Cavern Moccasin
Everliving Spore

The main challenge is not in the individual fights (like it was with the Celestial Touranment), because the fights are not very hard. The difficult part is the amount of fights that will slowly drain the number of full-health pets in your collection.
If you have a large collection of pets at your disposal, the challenge mode won't be hard for you.