We measure the decay B-s(0) -> K-0(K) over bar (0) using data collected at the Upsilon(5S) resonance with the Belle detector at the KEKB e(+)e(-) collider. The data sample used corresponds to an integrated luminosity of 121.4 fb(-1). We measure a branching fraction beta(B-s(0) -> K-0(K) over bar (0)) = [19.6(-5.1)(+5.8)(stat) +/- 1.0(syst) +/- 2.0(N-Bs0 (B) over bar s0)] x 10(-6) with a significance of 5.1 standard deviations. This measurement constitutes the first observation of this decay.