This story arc is very informative as it makes connections of other plots within World of Warcraft.  The Nightmare, the Old god C’thun and Hakkar the Soulflayer might be connected.  Molthor in Yojamba Isle(Stranglethorn Vale) refers to Hakkar the Soulflayer as a Faceless One.

Players of Warcraft III: The Frozen Throne may know what the Faceless Ones are, when Arthas and the Cryptlord King entered the Inner Kingdom of the Nerubian Caverns.  The Faceless Ones and the Forgotten One were buried deep below the Nerubian Kingdom for thousands of years, imprisoned.  The Earthquakes caused by Illidan with the Eye of Sargeras seem to have freed by accident the underground prison, when he attempted to crush the Icecrown to destroy the Lich King.  We also know that Flying Serpents are cousins of Hakkar.  The sons of Hakkar in Zul’Gurub are flying serpents. Furthermore, when summoning Dukes of the Abyssal Council in Silithus by the Twilight’s Hammer encampments—among these dukes are Flying serpents and Hydras—servants of the Old gods.

Back to subject, this below comes from a series of quests that start in Tanaris:

Spirit Screechers

Yeh’kinya: I seek the spirits of the vale screechers of Feralas. They are the cousins of an old, old god, and their spirits are linked to him.
Take this bramble wand and go to Feralas. Find and defeat vale screechers in southern and central Feralas, then wave my bramble over their fallen bodies. This will coax their spirit to reveal itself. Touch the spirit and collect its essence.
Return to me with my bramble and with the collected essence, and I will tell you more of the old god of which I spoke.

Note: Yeh’kinya is a Troll located at the Steamwheedle Port, northeastern Tanaris.

The Prophecy of Mosh’aru

Yeh’kinya: The ancient prophecy of Mosh’aru speaks of a way to contain the god Hakkar’s essence. It was written on two tablets and taken to the troll city of Zul’Farrak, west of Gadgetzan.

Bring me the Mosh’aru tablets!

The first tablet is held by the long-dead troll Theka the Martyr. It is said his persecutors were cursed into scarabs and now scuttle about his shrine.

The second tablet is held by the hydromancer Velratha, near the sacred pool of Gahz’rilla.

When you have the tablets, bring them to me.

The Ancient Egg

Yeh’kinya: The Prophecy of Mosh’aru speaks of an ancient egg. It is a relic of a time when trolls ruled vast empires, and it has the power to hold the essence of Hakkar. It may be the only way to keep our world safe from his evil.

Bring me the ancient egg. It is said to lay hidden deep within Jintha’Alor in the Hinterlands, in a cave behind the amphitheater at the top of the city.

The god Hakkar

Yeh’kinya: Now it is time to capture the essence of the avatar of Hakkar.

Take the Egg of Hakkar to the Sanctum of the Fallen God in the Sunken Temple in Azeroth. Invoke the egg’s power to stir the dead god.

He will send his minions against you. Defeat his bloodrinkers and take their Hakkari blood, then use the blood to dowse the eternal flames that hold Hakkar’s spirit. When all the flames go out, the avatar of Hakkar will enter our world.

Defeat him, and place his essence within the egg of Hakkar.

Note: You have to go to the Pool of Tears in eastern Swamp of Sorrows(Eastern Kingdoms).  There is a Sunken Temple in the middle of the Lake. You need five players. After you kill the Avatar of Hakkar and drain it by clicking the egg, return to Yeh’kinya.  If you talk again to him, he now will have an option:

Through my studies, I see that defeating the god Hakkar’s avatar has weakened him.  But the bulk of his strength remains, lurking at the far end of the Nether.

You have defeated his avatar once.  Perhaps if you defeat it again you can further weaken the god so that, one day, we might face his true self.

I have preapared a spell that you may use to again summon an avatar of Hakkar within the Sanctum of the Fallen god.  Do you want to confront it once again?

>Yes.  Give me the spell to summon the Avatar

The Lost Tablets of Mosh’aru

Prospector Ironboot: The troll with whom you spoke did not tell the truth. The two tablets you gained for him spoke of containing the essence of Hakkar, but there is more to that legend. I have studied long, and found that there are six Tablets of Mosh’aru, not two! Six!

And I fear that we will not like what secrets the others hold …

Find the third and fourth tablets of Mosh’aru. They’re in the Eastern Plaguelands, held by the Mossflayer trolls. Find them, and bring them to me.

The Final Tablets

Prospector Ironboot: While I look over the third and fourth tablets of Mosh’aru, you must find the fifth and sixth! It will not be easy, for they are held by the Smolderthorn trolls within Blackrock Spire. The spire is a dark mountain of fire between the Burning Steppes and the Searing Gorge.
Good luck. Blackrock Spire is no place for decent folk…

Confront Yeh’kinya

Prospector Ironboot in Steamwheedle Port, Tanaris

Prospector Ironboot: My delvings into the Mosh’aru Tablets bear grim news.  Hakkar’s true form, the god himself, can be born again through the very egg into which you captured him.  Yeh’kinya told you it was to contain his evil, but it is to recreate it!  The troll has led you astray!

Go to Yeh’kinya and demand the egg from him.  Pray that it is not too late to stop Hakkar’s return!

Confront Yeh’kinya – part 2

Yeh’kinya: So, you have been speaking with that old dwarf Ironboot and uncovered the lost Mosh’aru Tablets, have you?  That meddling prospector …

No matter.  It is too late to save this world.  Hakkar has been reborn, and even now grows in power … deep in the ancient troll kingdom of Zul’Gurub!  He has come!  And he will rule in blood and terror!

Thank you.  Your help has sped the return of the Soulflayer!

It is true.  The wheels of doom now turn, inevitably toward the true return of Hakkar!  Blood and souls for Hakkar!  HAHAHAHA!

Note: Strangely, Yeh’kinya shapeshifts into a Flying Serpent of Hakkar, a green ghostly form as if an emerald dream form; and flies away from you toward the east.

The Hand of Rastakhan

Prospector Ironboot: Our worst fears have come.  Legend speaks of the Soulflayer ruling the ancient troll world through evil and terror, and his power was absolute.  If he cannot be stopped now, then his new reign may spread across all of Azeroth!

There is a contingent of Zandalarian trolls who may help us stem this tide of darkness.  They have camped on Yojamba isle, off the coast of Stranglethorn, west of the ruins of Zul’Kunda.  Speak with their leader Molthor, and pray he knows how to defeat Hakkar.

The Hand of Rastakhan – part 2

Molthor: If you have come to save the world then you have come to the right place.  The Faceless One – the Blood god Hakkar—has been brought into our world!

You were sent by the prospector Ironbloot?  His kind are wise, and wiser still to bring you to me, for I and the Zandalarian trolls may know a way to defeat the Soulflayer.

Speak with the trolls of this isle, heed their words, and prepare yourself for the task before you is soaked in blood.

Altar of Zanza

Behind the troll village of Yojamba Isle is an altar of Zanza that reads:

We call upon you, Zanza of Zuldazar.

Bless those that ask for your help. Loa Zanza, Bless those that would ally with the Zandalarian people.

Aid us in this time of need.  Aid us Loa. Give us the power to strike down our enemis. Give us the power to once more defeat the Blood god.