The Ata'mal Terrace

The process of attunement to the Black Temple begins in Shadowmoon Valley with a very long quest chain that requires trips to the Arcatraz, Serpentshrine Cavern, Mount Hyjal and finally the doorstep of the Black Temple itself. Even if you're not planning on raiding just yet, the chain does offer some nice blue rewards half way through. It starts differently depending on whether you're Aldor (A) or Scryer (S):

Aldors pick up the line from Anchorite Ceyla in the Altar of Sha'tar:
1. (A) [70] Tablets of Baa'ri
2. (A) [70] Oronu the Elder
3. (A) [70] The Ashtongue Corruptors
4. (A) [70] The Warden's Cage

Scyers get it from Arcanist Thelis at the Sanctum of Stars:
1. (S) [70] Tablets of Baa'ri
2. (S) [70] Oronu the Elder
3. (S) [70] The Ashtongue Corruptors
4. (S) [70] The Warden's Cage

At this point the chains converge for both factions:
5. [70] Proof of Allegiance
6. [70] Akama
7. [70] Seer Udalo (Dungeon)

Here, you have to venture into the Arcatraz (which requires a Rogue with 350 lockpicking or somebody to open the door who's completed the Arcatraz Key chain, which requires trips to the Mechanar and the Botanica respectively) to the room just before the final boss. Sadly it's impossible to solo-stealth to. Finding Udalo leads to:

Talk to Akama:
8. [70] A Mysterious Portent
Kill waves of nonelites, 3 elites and a boss (5-man) on a terrace outside the Black Temple:
9. [70] The Ata'mal Terrace
Finally, deliver the medallion to A'dal in Shattrath City:
10. [70] Akama's Promise

The chain ends here, and you're granted a choice of rewards:
Akama's Sash (cloth DPS belt)
Bloodwarder's Rifle (gun)
Spellbreaker's Buckler (spelldamage shield)
Ashtongue Blade (phsyical DPS dagger)
Verdant Gloves (feral leather gloves)
Staff of the Ashtongue Deathsworn (healing staff)
However, if you now go into Serpentshrine Cavern and kill Karathress, you'll be able to talk to Seer Olum who'll continue the quest chain for you:

1. [70] The Secret Compromised
Go back to Warden's Cage in SMV and talk to Akama.
2. [70R] Ruse of the Ashtongue
Using the Ashtongue Cowl provided, kill Al'ar in Tempest Keep while disguised as a member of the Deathsworn.
3. [70R] An Artifact From the Past
You need to be attuned to Mount Hyjal for this. Simply kill Rage Winterchill and loot his phylactery (what is it with liches and their phylacteries?), then deliver it to Akama...
4. [70R] The Hostage Soul
...then return to Ad'al in Shattrath City...
5. [70R] Entry Into the Black Temple
...then go back to Shadowmoon and talk to Xi'ri on the road leading to the Black Temple. He'll ask you to help with
6. [70] A Distraction for Akama
...but once you tell Xi'ri you're ready (talk to him after accepting the quest), you can watch a scripted sequence that you do not actually have to help with in any way. After this is finished, talk to Xi'ri again for your Medallion of Karabor and the completion of Black Temple attunement. Congratulations, you can now waltz in to Illidan's latest bachelor pad!

But before you go, the chain continues from Xi'ri with:
7. [70R] Seek Out the Ashtongue
Time to start exploring the Black Temple! When you find the Deathsworn, they'll give you
2. [70R] Redemption of the Ashtongue
...which requires you to kill the Shade of Akama. Finally you're given
3. [70R] The Fall of the Betrayer
Yup, kill Illidan. No problem. Then you're done.

Heres a cheese way to do it:

1) Bring a ranged lvl 70 class that can reach 36-41 yards
2) Fly on top of the building and start plugging away at the soulstealers. They will not evade.
3) The spawn waves will come out but won't attack you on top of the building.
4) Shadowlord Deathwail will now land when the soulstealers are all dead, just wait a few minutes for the spawns to disappear then you can fight him all alone.

Note: I tried this solo but i did not attempt to fully fight him. I attacked him from on top of the building and he did not evade since he does a ranged shadowbolt that only hits for ~1k.

It may be possible to ranged tank him from the roof while taking no physical damage if your group lacks a warrior/druid/pally tank. Though his melee only hit for 900ish on cloth

71,35. Kill the 3 elites channeling the heart. Some none elite adds will spawn when you start attacking each elite. Kill Shadowlord Deathwail for the heart.
Shadowlord Deathwail http://www.wowhead.com/?npc=22006
Followup http://www.wowhead.com/?quest=10708