The M-ellipsoid of a convex body K is a fundamental object introduced by V. Milman. It has the same volume as K and can cover K with the union a small number of translations. There are several proofs of the existence of an M-ellipsoid. We present algorithms for constructing M-ellipsoids based on two of these proofs. The first is randomized and is via a proof by Klartag giving optimal covering bounds. The second, based on a proof by Pisier, achieves slightly weaker bounds but leads to a deterministic algorithm. We use M-ellipsoids in a new algorithm for enumerating lattice points in a convex body. This has several consequences, including more efficient algorithms for (a) the shortest vector problem in any semi-norm (distance induced by a convex body) (b) integer programming (c) deterministic approximate volume computation. This is joint work with Daniel Dadush and Chris Peikert.