There is a notion of "non-commutative Lie algebra" called Leibniz algebra, which is characterized by the condition: left bracketing is a derivation. The purpose of this article is to introduce and study a new notion of algebra, called dialgebra, which is, to the Leibniz algebras, what associative algebras are for Lie algebras. A dialgebra is a vector space equipped with two associative operations satisfying three more conditions. For instance, any differential associative algebra gives rise to a dialgebra. In this article we construct and study a (co)homology theory for dialgebras. The surprising fact, in the construction of the chain complex, is the appearance of the combinatorics of planar binary trees (grafting and nesting). The principal result about this homology theory is its vanishing on free dialgebras. The Koszul dual (in the sense of Ginzburg and Kapranov) of the operad of dialgebras is the operad of dendric algebras. The dendric algebras are characterized by two operations satisfying three linear conditions. The sum of these two operations defines a new operation which is associative. The free dendric algebras can be described in terms of planar binary trees. As a consequence we give an explicitly description of strong homotopy dialgebras. This paper is part of a long-standing project whose ultimate aim is to study periodicity phenomenons in algebraic K-theory, as explained in "Overview on Leibniz algebras, dialgebras and their homology". Fields Inst. Commun. 17 (1997), 91--102.