The new ternary phase Ba(5)In(4)Bi(5) was synthesized by direct reaction of the corresponding elements at high temperature. It crystallizes in a noncentrosymmetric space group and represents a new structure type (tetragonal, P4nc with a=10.620(2) and c=9.009(2) A, Z=2). The structure is built of interconnected heteroatomic clusters of In(4)Bi(5), square pyramids with In(4)-bases and four exo-bonded bismuth atoms (bond to the In atoms). According to Wade's rule the compound is electron-deficient with one electron per cluster, that is, [In(4)Bi(5)](10-) instead of the expected [In(4)Bi(5)](11-) for a closed-shell species. The clusters are discussed also in light of the known heteroatomic deltahedral clusters with the same composition but different charge, [In(4)Bi(5)](3-). Band structure calculations on the new compound suggest substantial participation of barium in the overall bonding of the structure that "accounts" for the electron shortage