We investigate the complexity of embeddings between bi-embeddable structures. In analogy with categoricity spectra, we define the bi-embeddable categoricity spectrum of a structure \$\textbackslashmathcal A\$ as the family of Turing degrees that compute embeddings between any computable bi-embeddable copies of \$\textbackslashmathcal A\$; the degree of bi-embeddable categoricity of \$\textbackslashmathcal A\$ is the least degree in this spectrum (if it exists). We extend many known results about categoricity spectra to the case of bi-embeddability. In particular, we exhibit structures without degree of bi-embeddable categoricity, and we show that every degree d.c.e. above \$\textbackslashmathbf{0}\^{(\textbackslashalpha)}\$ for \$\textbackslashalpha\$ a computable successor ordinal and \$\textbackslashmathbf{0}\^{(\textbackslashlambda)}\$ for \$\textbackslashlambda\$ a computable limit ordinal is a degree of bi-embeddable categoricity. We also give examples of families of degrees that are not bi-embeddable categoricity spectra.