The Arena is available after the Main Story. You'll be introduced to the Arena in the Character Quests at the beginning - you fight Moses in there.
You can find the Arena on the lower floors of the Inn in Werites Beacon.
Hope this'll help you out somehow.