Welcome to Zuldazar

You have to follow her all the way, you can't run ahead. If you run too far away, she will respawn at the docks.

"Dat is far enough, Horde scum... Oh, and here be two gold for you."

The Warchief Awaits popped up after first login with a level 110 toon one week after prepatch for BfA.
If you completed the story with one character (of the same faction), you can talk to Sylvanas "I have heard this tale before" to skip the chain after accepting The Warchief Commands (step 2). You'll get teleported to the south of Darkshore with access to World Quests.
You will need to complete the previous chapters to unlock the following ones (chapter 1, The Battle for Lordaeron (chapter 3, step 2) and The Stormwind Extraction (chapter 4, step 6) can be skipped after completing it once).

Chapter 1 (unlocked 07/24/2018):

1. 
   
2. The Warchief Awaits - meet [npc=134554] in Undercity (use the middle doorway in the Apothecarium to reach her -> /way Undercity 53.22 62.73 Entrance). Don't use the teleporter from Silvermoon to go to Uc, this might kill you
3. 
   
4. The Warchief Commands - travel to Crossroads and meet [npc=134574] - you can skip this step and the rest of this chapter, if you completed it on an other character before
5. 
   
6. A Quick Diversion - travel to Astranaar in Ashenvale and meet [npc=134573]
7. 
   
8. Everybody Has a Price - dismount and use your extrabutton to mark the guards
9. 
   
10. A Timely Arrival - meet [npc=135003]
11. 
    
12. Zoram'gar Outpost - fly to Zoram'gar Outpost and speak to the mentioned NPC. Return to Astranaar
13. 
    
14. On The Prowl - turn in at the border between Ashenvale and Darkshore
15. 
    
16. Into the Woods - kill 6 enemies
17. 
    
18. Ripe for the Picking - return to Zoram'gar Outpost
19. 
    
20. A Quick Flyover - speak to [npc=135501] and kill wisps and trees
21. 
    
22. An Unstoppable Force - return to the border to Darkshore, pass the wall and wait for Sylvanas. Reload, if she doesn't appear for you
23. 
    
24. A Glaive Misunderstanding - burn glaives with your [item=158937]
    Clearing Them Out - kill 7 elfs
25. 
    
26. Blurred Vision - kill 8 owls and 10 furbolgs
27. 
    
28. The Trees Have Ears - kill [npc=141365] (cinematic after turn in)
29. 
    
30. The Blackwood Den - kill 10 furbolgs
    Aggressive Inspiration - place 3 banners
31. 
    
32. The Start of Something Good - return to Zoram'gar Outpost
33. 
    
34. A Very Clear Message - kill 10 elfs
    Fueling the Horde War Machine - collect Azerite lying around
35. 
    
36. A Gift of Azerite - turn in at the marked area
37. 
    
38. A Wild Ride - click [npc=141847], it will transport you. Kill enemies
39. 
    
40. A Looming Threat - return to Sylvanas and click her dialogue
    After that 4 World Quests in Darkshore popped up.
41. 
    

It took around 40 minutes.

---

Chapter 2 (unlocked on 07/31/2018):

1. 
   
2. Saurfang Returns - find Saurfang (I got this quest after entering Darkshore)
3. 
   
4. No Small Mercy - click 8 citizens
   Seaside Rendezvous - kill 2 named NPC ([npc=142749] and [npc=144345])
   Driving Them Out - kill 15 defenders
5. 
   
6. Killer Queen - fly to the marked area, find Saurfang, watch roleplay and meet Sylvanas at the beach (45.52, 18.26). Click her dialogue (cinematic)
7. 
   

It took around 11 minutes, starting at Darkshore's south & without cinematic.

You will gain [item=163128] (teaches Undercity Plaguebat) at the end (reward from Killer Queen) and also get Teldrassil Hippogryph ([item=163127]) for the other faction at the same time. So you only need to complete the quest chain on one faction to get both mounts, but they are bound to their faction.

---

Chapter 3 (unlocked on 08/07/2018):

1. 12.00
   
2. [quest=53372] - meet [npc=14720] (popped up after login)
3. 
   
4. The Battle for Lordaeron - speak to Isabella on the left side, click the dialoge to start the scenario (20 man)- you can skip this scenario, if you completed it on an other character before
   - kill enemies to fill the bar
   - follow Saurfang and help him to go to the middle of Undercity
   - click the dialogue of Uc's citizens to fill the bar
   - use [npc=131087] below the bank
   - follow Saurfang and kill all enemies in front of Undercity (3 waves) (cinematic when done)
   - speak to a [npc=133115] to get [spell=261724]. Click [npc=127065] to fill the bar (cinematic)
   - follow [npc=133243]
   - fight against the Alliance (cinematic)
   - follow [npc=133243] again
   - wait for her and follow [npc=130365] (cinematic). You'll get transported to Og after that
5. 
   

It took ca. 27 minutes, starting in Og at Saurfang (ca. 21 without cinematics)

---

Chapter 4 (unlocked on BfA Release):

1. 9.24
   
2. A Dying World - travel to Silithus and meet Magni (popped up after login). Speak to Zidormi, if you changed the phasing in Silithus
3. 
   
4. The Heart of Azeroth - follow Magni to the translocator and click the console's dialogue (cinematic). Speak to Magni
   You will get [item=158075] and Have a Heart
5. 
   
6. Infusing the Heart - use your extrabutton [spell=275825] at the azerite ores to fill the bar, go to the middle and click it again
7. 
   
8. [quest=53031] - go to Orgrimmar (use the transporter behind Magni) and meet [npc=140176]
9. 
   
10. Battle for Azeroth: Mission Statement - enter Grommash Hold (cinematic) and meet your team in the inn
11. 
    
12. The Stormwind Extraction - click [item=160251] on the table and go to the wall. Click [npc=135211], it will transport you to the solo scenario (you can skip this scenario, if you completed the chapter on an other character before and continue with step 7):
    - destroy the two padlocks and enter Stormwind's sewer
    - go to the marked area and meet Rokhan
    - click the door, speak to [npc=134120] (wait for his dialogue is complete before you open the next door. Might bug otherwise)
    - go to the mark on the other side, click the door to free the Zandalaris. Follow and defend your team on the way to the northeastern part of the dungeon. Click [npc=139948]
    - speak to Rokhan and follow him. Speak to him again after you jumped into the water, follow again
    - kill attackers and follow your team and speak to Nathanos Blightcaller. Follow again
    - destroy [npc=134881]
    - kill enemies on your way to the nothern dock. Enter your ship and speak to Princess Talanji (cinematic)
13. 
    
14. Welcome to Zuldazar - follow Princess Talanji
15. 
    
16. Rastakhan - click [npc=135438], it will transport you to the princess. Talk to her (cinematic)
17. 
    
18. Speaker of the Horde - speak to Zolani and follow her. Use the elevator and click [npc=121000] at the balcony
    Re-enter the building and visit the tree chambers. Turn in at the other room at the floor
19. 
    
20. [quest=52139] - meet the princess
21. 
    
22. We Need Each Other cinematic. You get Welcome to Zandalar after turning in
    Quest line done - now you can chose your preferred quest area at the map on the table
23. 
    

It took ca. 55 minutes (ca. 50 without cinematics)

---

There are portals to capitals after completion: Inside of the pyramide at the bottom /way 52.83 71.0 Entrance to portals for Silvermoon City (Burning Crusade), Orgrimmar, Thunder Bluff
Portal in Orgrimmar to Zuldazar in the Cleft of Shadows near the portal to Dalaran.