The notion of a conformal algebra encodes an axiomatic description of the operator product expansion of chiral fields in conformal field theory. On the other hand, it is an adequate tool for the study of infinite-dimensional Lie algebras satisfying the locality property. The main examples of such Lie algebras are those "based" on the punctured complex plane, such as the Virasoro algebra and loop Lie algebras. In the present paper we develop a cohomology theory of conformal algebras with coefficients in an arbitrary module. It possesses standards properties of cohomology theories; for example, it describes extensions and deformations. We offer explicit computations for the most important examples.