We consider a weakly interacting quantum spin chain with random local interactions. We prove that many-body localization follows from a physically reasonable assumption that limits the extent of level attraction in the statistics of eigenvalues. In a KAM-style construction, a sequence of local unitary transformations is used to diagonalize the Hamiltonian by deforming the initial tensor product basis into a complete set of exact many-body eigenfunctions.