When estimating the distributions of two random variables, X and Y, investigators often have prior information that Y tends to be bigger than X. To formalize this prior belief, one could potentially assume stochastic ordering between X and Y, which implies Pr(X < or = z) > or = Pr(Y < or = z) for all z in the domain of X and Y. Stochastic ordering is quite restrictive, though, and this article focuses instead on Bayesian estimation of the distribution functions of X and Y under the weaker stochastic precedence constraint, Pr(X < or = Y) > or = 0.5. We consider the case where both X and Y are categorical variables with common support and develop a Gibbs sampling algorithm for posterior computation. The method is then generalized to the case where X and Y are survival times. The proposed approach is illustrated using data on survival after tumor removal for patients with malignant melanoma.