We report the first observation of the decay (B) over bar (0)-> D-s(+)Lambda(p) over bar with a statistical significance of 6.6 sigma. We measure B((B) over bar (0)-> D-s(+)Lambda(p) over bar)=(2.9 +/- 0.7 +/- 0.5 +/- 0.4)x10(-5), where the first error is statistical, the second is systematic, and the third error comes from the uncertainty in B(D-s(+)->phi pi(+)). The data used for this analysis was accumulated at the Upsilon(4S) resonance, using the Belle detector at the KEKB asymmetric-energy e(+)e(-) collider. The integrated luminosity of the data sample is 414 fb(-1), corresponding to 449x10(6) B (B) over bar pairs.