A new ternary selenostannate Ba6Sn6Se13 has been synthesized by a high temperature solid-state method. The compound crystallizes in the non-centrosymmetric orthorhombic space group P2(1)2(1)2(1) and may be represented as Ba6Sn5(2+)Sn(4+)Se13 with mixed valence Sn atoms. Sn(4+) cations lie in a tetrahedral environment, while Sn(2+) cations are found in two kinds of coordination environments: the trigonal pyramid and quadrangular pyramid. SnSe(n) (n = 3, 4, 5) polyhedra are further connected to generate a three-dimensional framework with Ba(2+) residing in cavities. Ba6Sn6Se13 shows moderate nonlinear optical response and is the first reported NLO compound in the Ba-Sn-Se system. In addition, diffuse reflectance spectroscopy measurement indicates that the band gap of Ba6Sn6Se13 is 1.52(2) eV and thermal analysis suggests that the compound melts incongruently. The theoretically calculated SHG response and band gap are in good agreement with experimental results.