Alice and Bob notation is a popular way to describe security protocols: it is intuitive, succinct, and yet expressive. Several formal protocol specification languages are based on this notation. One of the most severe limitations of these languages is the lack of algebraic reasoning, which is required for instance for the correct interpretation of Diffie-Hellman based protocols. As a consequence, previous approaches either cannot handle such protocols at all or require manual annotation. We generalize previous approaches and give the first formal semantics for a language based on Alice and Bob notation that is defined over an arbitrary algebraic theory. In particular, it defines unambiguously how the protocol is supposed to be executed by honest agents, based on the considered algebraic properties of the operators.