Matrix completion is a fundamental problem that comes up in a variety of applications like the Netflix problem, collaborative filtering and crowdsourcing. The goal of the problem is to recover a k-by-n unknown matrix from a subset of its entries. We define an information-theoretic notion of completion capacity C that quantifies the maximum number of entries that one observation of an entry can reveal. This number provides the minimum number of entries required for reliable reconstruction: kn/C. Translating the problem into a distributed joint source-channel coding problem with encoder restriction, we characterize the completion capacity for a wide class of stochastic models of the unknown matrix and the observation process, and also derive an upper bound for an arbitrary stochastic matrix.