Embassy (and Ambassador) and its Spanish equivalent, Embajada (and Embajador), both come from the same ancestor, the Old French Ambactos.
What is most interesting about these two is that it is an example of the pattern where the -j- sound in Spanish maps to the -sh- sound (and its cousins, like -ss- and -ch-) in English. Remember syrup and jarabe, chess and ajedrez, sherry and jerez, and push and empujar for a few examples.
Thus, the m-b-j of emabajada maps to the m-b-ss of embassy.