The Scarlet Basilica is a large cathedral located inside Tyr's Hand in the Eastern Plaguelands. It is the high seat of religious power for the Scarlet Crusade and has close ties to Tyr's Hand Abbey nearby as well as the Scarlet Monastery much further west in Tirisfal Glades. It is the location of Crusader Lord Valdelmar.
In the RPG
This section contains information from the Warcraft RPG which is considered non-canon.
The basilica of Tyr's Hand was instead said to actually be the Scarlet Monastery and to have been newly-erected.