We report the first observation of the decays B-0 -> p (Lambda) over barD(*)(-). The data sample of 711 fb(-1) used in this analysis corresponds to 772 x 10(6) B (B) over bar pairs, collected at the Upsilon(4S) resonance by the Belle detector at the KEKB asymmetric-energy e(+)e(-) collider. We observe 19.8 sigma and 10.8 sigma excesses of events for the two decay modes and measure the branching fractions of B-0 -> p (Lambda) over barD(-) and B-0 -> p (Lambda) over barD*(-) to be (25.1 +/- 2.6 +/- 3.5) x 10(-6) and (33.6 +/- 6.3 +/- 4.4) x 10(-6), respectively, where the first uncertainties are statistical and the second are systematic. These results are not compatible with the predictions based on the generalized factorization approach. In addition, a threshold enhancement in the dibaryon (p (Lambda) over bar) system is observed, consistent with that observed in similar B decays.