Ketika kabar kekalahan pasukan Muslim[[Bangsa Arab|Arab]] dalam melawan pemberontak [[Berber]] di [[Pertempuran Para Bangsawan]] sampai kepada Khalifah [[Hisyam bin Abdul-Malik]], ia memecat gubernur [[Ifriqiyah]] [[Ubaidillah bin Al-Habhab]] dan menggantinya dengan [[Kultsum bin Iyadh al-Qusyairi]].<ref name="Andalusia">{{cite book|title=Bangkit dan Runtuhnya Andalusia|date=2013|format=Bukel|publisher=Pustaka Al-Kautsar|author=Prof. Dr. Raghib As-Sirjani|page=135|ref=harv|url=https://books.google.co.id/books?id=T7_cDwAAQBAJ&pg=PA135&dq=kaltsum+bin+iyadh&hl=id&newbks=1&newbks_redir=0&source=gb_mobile_search&sa=X&ved=2ahUKEwixibaHtZn_AhXE-DgGHfVlAKAQ6AF6BAgDEAM#v=onepage&q=kaltsum%20bin%20iyadh&f=false|access-date=2023-05-29|archive-date=2023-05-29|archive-url=https://web.archive.org/web/20230529015238/https://books.google.co.id/books?id=T7_cDwAAQBAJ&pg=PA135&dq=kaltsum+bin+iyadh&hl=id&newbks=1&newbks_redir=0&source=gb_mobile_search&sa=X&ved=2ahUKEwixibaHtZn_AhXE-DgGHfVlAKAQ6AF6BAgDEAM#v=onepage&q=kaltsum%20bin%20iyadh&f=false|dead-url=no}}</ref> Kultsum berangkat ke Ifriqiyah dengan 30.000 pasukan didampingi oleh keponakannya, Balj bin Bisyr dan Tsa'labah sendiri.<ref name="Andalusia" /> Pertempuran kemudian pecah antara pasukan Kultsum dan pemberontak Berber di [[Pertempuran Bagdoura]].<ref name="Ta'rif">{{cite web|title=Kitab Ta'rif bil Amakin Al-Waridat fi Al-Bidayah wan Nihayah oleh Ibnu Katsir - Bagdoura - Al-Maktaba al-Shamela|page=343|author-link=|language=ar|website=shamela.ws|url=https://shamela.ws/book/429/326|access-date=2023-05-30|archive-date=2023-05-30|archive-url=https://web.archive.org/web/20230530145048/https://shamela.ws/book/429/326|dead-url=no}}</ref>
Setelah pasukan Kultsum mengalami kekalahan, Balj bin Bisyr membawa pasukan yang tersisa ke [[Ceuta]] lalu menyeberang ke [[Al-Andalus]].{{sfn|Prof. Dr. Raghib As-Sirjani|2013|p=135–137}} Di sana ia sempat membantu gubernurnya, [[Abdul Malik bin Qathan Al-Fihri]] dalam melawan pemberontakan Berber yang pecah di Al-Andalus.{{sfn|Prof. Dr. Raghib As-Sirjani|2013|p=137}} Balj kemudian berselisih dengan Abdul Malik dan menganggap bahwa dirinya merupakan gubernur Al-Andalus. Tsa'labah bin Salamah mendukung pendapat Balj.{{sfn|Prof. Dr. Raghib As-Sirjani|2013|p=137–138}} Abdul Malik kemudian ditangkap lalu disalib yang berujung pada pembunuhannya.{{sfn|Prof. Dr. Raghib As-Sirjani|2013|p=138}}
