We investigate constraints imposed by entanglement on gravity in the context of holography. First, by demanding that relative entropy is positive and using the Ryu-Takayanagi entropy functional, we find certain constraints at a nonlinear level for the dual gravity. Second, by considering Gauss-Bonnet gravity, we show that for a class of small perturbations around the vacuum state, the positivity of the two point function of the field theory stress tensor guarantees the positivity of the relative entropy. Further, if we impose that the entangling surface closes off smoothly in the bulk interior, we find restrictions on the coupling constant in Gauss-Bonnet gravity. We also give an example of an anisotropic excited state in an unstable phase with broken conformal invariance which leads to a negative relative entropy.