In this article we disprove the conjectures asserting the positivity of the coefficients of the Ehrhart polynomial of matroid polytopes by De Loera, Haws and Koppe (2007) and of generalized permutohedra by Castillo and Liu (2015). We prove constructively that for every n > 19 there exist connected matroids on n elements that are not Ehrhart positive. Also, we prove that for every k > 3 there exist connected matroids of rank k that are not Ehrhart positive. Our proofs rely on our previous results on the geometric interpretation of the operation of circuit-hyperplane relaxation and our formulas for the Ehrhart polynomials of hypersimplices and minimal matroids. This allows us to give a precise expression for the Ehrhart polynomials of all sparse paving matroids, a class of matroids which is conjectured to be predominant and which contains the counterexamples arising from our construction.