We introduce decomposition algebras as a natural generalization of axial algebras, Majorana algebras and the Griess algebra. They remedy three limitations of axial algebras: (1) They separate fusion laws from specific values in a field, thereby allowing repetition of eigenvalues; (2) They allow for decompositions that do not arise from multiplication by idempotents; (3) They admit a natural notion of homomorphisms, making them into a nice category. We exploit these facts to strengthen the connection between axial algebras and groups. In particular, we provide a definition of a universal Miyamoto group which makes this connection functorial under some mild assumptions. We illustrate our theory by explaining how representation theory and association schemes can help to build a decomposition algebra for a given (permutation) group. This construction leads to a large number of examples. We also take the opportunity to fix some terminology in this rapidly expanding subject.