We discuss the Zamolodchikov-Faddeev algebra for the superstring sigma-model on AdS5 x S5. We find the canonical su(2,2)2 invariant S-matrix satisfying the standard Yang-Baxter and crossing symmetry equations. Its near-plane-wave expansion matches exactly the leading order term recently obtained by the direct perturbative computation. We also show that the S-matrix obtained by Beisert in the gauge theory framework does not satisfy the standard Yang-Baxter equation, and, as a consequence, the corresponding ZF algebra is twisted. The S-matrices in gauge and string theories however are physically equivalent and related by a non-local transformation of the basis states which is explicitly constructed.