Story related, can’t be missed.
The Reds are found in the Nordberg Sanctuary. After returning to your Netherworld Tower for the first time and getting the quest to conquer Nordberg you’ll have to head in. When inside just on your left is a Netherworld shard, select it with and send your minions to it with then hit to gain control of a minion. Lead them over the bridge with the Dryad and take the path to the right to get around to kill her. Afterward hold to return to your Overlord and get across the, now clear, bridge.
Follow the path down and you’ll come to a Netherworld gate and another Dryad, you can’t pass here yet so head right and slide down a dirt ramp. You’ll cross some water and have to leave your minions behind, after this there’s a Dark Crystal  on your left. Continue on the path until you find some red minions who’ll join you after a cutscene. Send them to destroy the barrier with and follow the path once more.
To your right is a room with treasure and two carnivorous plants, stock up if you want then destroy the other barrier to continue on. You’ll come to a lift, which will activate when you step on it with two more plants just as you step off. Slide down the dirt ramp to find the Dryad once more, take 10 browns out from the nearby minion portal and kill her then place your reds on a guard marker with on the nearby ledge to kill the second dryad below allowing your to advance.
Follow the path around, fighting some elves on the way, to reach another lift. Follow the next path around through a series of balconies until you come to another lift that heads down with elves on board. Continue on past the Harp (Grab it as a Netherworld gate is just around the corner) to find another Netherworld Shard allowing you to take control of a minion. The path to take is just opposite the shard room slowing you to raise the lift for the Overlord.
Head down to the lift and around to the statue with three dryads and some long grass in front of it. Only use your reds here as the grass will burn killing your browns and injuring you. Destroy the Statues and the Crystal that drops for a Mana upgrade. Grab it and head over the fallen statue to find the Red Minion Hive, there is a Netherworld gate just behind a barrier in the same room to carry it into.