魏賽因不花幼年卓而不群，善于騎射。至正年間，紅巾起義開始，他應朝廷之募義勇，成為察罕帖木兒的部將，曾經單騎殺敵百餘人。至正十九年（1359年），參與進攻汴梁（今河南省開封市）紅巾軍，擊退劉福通。從王保保（擴廓帖木兒）擊敗中書省右丞相孛羅帖木兒于大同。至正二十五年（1365年），孛羅帖木兒敗亡，任河南江北知樞密院事，奉命和嶺北行省左丞相山僧追擊他的餘黨禿堅帖木兒。至正二十八年（1368年），王保保派兵據守太原，殺盡元朝留守的官員。元順帝派他和李思齊、張良弼等人率軍在澤州（今山西省晉城市）夾擊王保保，在澤州城下，拜為中書平章政事，進兵攻打晉寧路（今山西省臨汾市），不久卒。