The first observation of the decay B-s(0) -> phi(K) over bar*(0) is reported. The analysis is based on a data sample corresponding to an integrated luminosity of 1.0 fb(-1) of p p collisions at root s = 7 TeV, collected with the LHCb detector. A yield of 30 +/- 6 B-s(0) -> (K+ K-)(K- pi(+)) decays is found in the mass windows 1012.5 < M (K+ K-) < 1026.5MeV/c(2) and 746 < M (K- pi(+)) < 1046MeV/c(2). The signal yield is found to be dominated by B-s(0) -> phi(K) over bar*(0) decays, and the corresponding branching fraction is measured to be B (B-s(0) (->) phi(K) over bar*(0)) = (1.10 +/- 0.24 (stat) +/- 0.14 (syst) +/- 0.08 (f(d)/f(s))) x 10(-6), where the uncertainties are statistical, systematic and from the ratio of fragmentation fractions f(d)/f(s) which accounts for the different production rate of B-0 and B-s(0) mesons. The significance of B-s(0) ->phi (K) over bar*(0) signal is 6.1 standard deviations. The fraction of longitudinal polarization in B-s(0) -> phi(K) over bar*(0) decays is found to be f(0) = 0.51 +/- 0.15 (stat) +/- 0.07 (syst).