A new theory of concurrent objects is presented. The theory has the important advantage of being based directly on a logic called rewriting logic in which concurrent object-oriented computation exactly corresponds to logical deduction. This deduction is performed by concurrent rewriting modulo structural axioms of associativity, commutativity and identity that capture abstractly the essential aspects of communication in a distributed object-oriented configuration made up of concurrent objects and messages. Thanks to this axiomatization, it becomes possible to study the behavior of concurrent objects by formal methods in a logic intrinsic to their computation. The relationship with Actors and with other models of concurrent computation is also discussed. A direct fruit of this theory is a new language, called Maude, to program concurrent object-oriented modules in an entirely declarative way using rewriting logic; modules written in this language are used to illustrate the main ideas with examples. Maude contains OBJ3 as a functional sublanguage and provides a simple and semantically rigorous integration of functional programming and concurrent object-oriented programming.