Well if you want the story of the entire world just say, but for now, since you're asking about the Howling Abyss, I'll focus on that.
So a long arse time ago humans, trolls, ursine, yetis, they all lived in the Freljord doing whatever. The woman you heard? She was a human called Lissandra (Yes that Lissandra), and had two sisters named Avarosa and Serylda. They lived as good lives as you can in the Freljord, which is to say every day was a struggle. Lissandra actually recieved a horrific wound from an ursine, permanently blinding her.
Then the Frozen Watchers arrive. No one knows where they came from, but they were powerful. Extremely so. They approached the humans of the Freljord and granted them immortality and immense power, but at a price; in exchange they would willingly serve the Watcher's, and do for them whatever they wanted. To that end the humans, who at this point had been given the name "iceborn", did exactly that, which culminated in them conquering the entirety of Freljord and Valoran, plunging the world in to an iceage. The Howling Abyss, along with many other structures in the Freljord were made by the Iceborn for the Frozen Watchers; the various statues on the bridge's side, the looming figure on the gate and even the turrets on the map were made in the Watcher's image.
Lissandra, Avarosa and Serylda had all been transformed and were Iceborn at this point. Thanks to this Lissandra actually had the ability to compensate for her blindness, as through the ice she could sense movement and shapes. She was eternally grateful and became
the "Seeker", the personal who spoke for the Frozen Watchers for the iceborn. Things went well for a time, but eventually Avarosa was no longer content to serve. Believing they were essentially being used as slaves she rallied the iceborn against the Frozen Watchers, culminating in a war that ended at the Howling Abyss. On one side Watchers, on the other Avarosa's army. Many died, but eventually the iceborn over ran their enemies, and tossed the watchers howling in to the abyss. The bridge was renamed and Greyor, one of Avarosa's faithful warriors, pledged he'd watch over the area and sound the
Guardian's Horn just in case the Watcher's had survived the fall and ever climbed out of the Abyss.
Avarosa went on to lead the Iceborn's civilisation as the
Frost Queen, but Lissandra wasn't happy. Neither was Serylda really, but Lissandra was royally pissed because she truly believed in the Watcher's and their ways, and this whole thing felt like a massive betrayal by her sisters. Serylda disagreed with Avarosa's choices in leadership, and eventually civil war broke out among the Iceborn, with Avarosa, Serylda and Lissandra duking it out. This war, the War of the Three Sisters, ended up with no clear victor as Avarosa was killed thanks to Lissandra's plots, Serylda's fate remains unknown, and the whole empire was shattered. The iceborn were scattered, and eventually faded away as, if I'm remembering/interpreting correctly, the iceborn couldn't procreate to make more of their kind, instead birthing humans with lingering magic in their veins. As a result they disappeared from the world as their numbers began to dwindle, and the Freljord returned to the state it was in before the Frozen Watchers came; a land engulfed by war where only the strong could even hope to etch out a living.
Lissandra had done what she needed to do, and set in motion a plan to bring the Watcher's back. She killed the leader of a tribe known as the Frostguard in secret and assumed their position through icy shapeshifting. Over the course of the years she corrupted the tribe and had them collect or destroy Freljord's ancient history, to ensure none would remember the past enough to be able to stop her. To keep the facade that she was human and could be trusted by tribes on the outside, she would name a successor, fake her own death, kill the successor and then impersonate them, ensuring her continued rule of the tribe.
That's the ancient history of Freljord as far as I remember it. How that affects the modern day is quite the thing, but something that might be better off not elaborating on right now.