Withal first appeared on an island controlled by the Crippled God. He was told that he would be set free once he had fashioned a sword for the god and was given the company of three Nachts: Rind, Mape, and Pule.
On that same island, Withal later met Rhulad Sengar, who eventually became the wielder of the cursed sword.
The Crippled God, concerned for the well-being of his captive, resurrected the Tiste Andii Sandalath Drukorlat in order to provide Withal with female companionship. Mael arrived on the island upon which Withal and Sand were captive and brought a boat in which they and the Nachts escape.
Despite her physical and verbal abuse toward him, Withal eventually married Sand.
Withal lived in Malaz City and was known as Foreigner at Coop's Hanged Man Inn. When the Fourteenth Army sailed into the Malaz Bay, Tavore commissioned Bottle to find an unnamed person and bring him back to the Froth Wolf. Bottle had not arrived when it was time to leave the island. Tavore said that unless Bottle returned with his charge, the trip to Malaz City was a failure. That person was Withal.
Withal and Sandalath travelled and stayed at the island of the Shake.
Withal accompanied Sandalath as she pursued the Shake into Kurald Galain where she was once held hostage.
Withal tried to keep Sandalath sane as she relived the horrors of life in Kharkanas before the Andii exodus. Her crippling memories and the loss of her son proved to be too much for him to heal, and Withal left her on the throne to help defend the First Shore with the Shake. He fought during the final stand of the Shake, surviving with Yan Tovis to witness the return of the Tiste Andii to Kharkanas.