Notch signaling pathway defines an evolutionarily conserved mechanism in cell-fate determination in a broad spectrum of developmental processes through local cell interactions. mind bomb (mib) encodes an E3 ubiquitin ligase that is involved in Notch activation through Delta ubiquitylation and internalization. To further dissect the function of Mib, two yeast two-hybrid screens for zebrafish Mib/Mib2-binding proteins with different strategies have been performed. 81 putative interesting proteins were discovered and classified into six groups: ubiquitin proteasome pathway, cytoskeleton, trafficking, replication/transcription/translation factors, cell signaling and others. Confirmed by coimmunoprecipitation (Co-IP), Mib interacted with four tested proteins: ubiquitin specific protease 1 (Usp1), ubiquitin specific protease 9 (Usp9), tumor-necrosis-factor-receptor-associated factor (TRAF)-binding domain (Trabid)/zinc finger, RAN-binding domain containing 1 (Zranb1) and hypoxia-inducible factor 1, alpha subunit inhibitor (Hif1an)/factor inhibiting HIF 1 (Fih-1). Usp1, Usp9, Trabid and Fih-1 also bound to zebrafish Mib2, a Mib homolog with similar structural domains and functions. Both Mib and Mib2 can ubiquitylate Trabid and Fih-1, indicating a potential regulating role of Mib and Mib2 on Trabid and Fih-1 and, furthermore, the possible involvement of Notch signaling in hypoxia-regulated differentiation, tumorigenesis and NF-κB pathway. Finally, functions of confirmed Mib/Mib2-interacting proteins are collated, summarized and hypothesized, which depicts a regulating network beyond Notch signaling.