The notion of relations is extremely important in mathematics. In this paper, we use relations to describe the embedding problem and propose a novel stochastic relational model for nonlinear embedding. Given some relation among points in a high-dimensional space, we start from preserving the same relation in a low embedded space and model the relation as probabilistic distributions over these two spaces, respectively. We illustrate that the stochastic neighbor embedding and the Gaussian process latent variable model can be derived from our relational model. Moreover we devise a new stochastic embedding model and refer to it as Bernoulli relational embedding (BRE). BRE?s ability in nonlinear dimensionality reduction is illustrated on a set of synthetic data and collections of bitmaps of handwritten digits and face images.