We design and analyze a Hybrid High-Order (HHO) method on unfitted meshes to approximate elliptic interface problems. The curved interface can cut through the mesh cells in a very general fashion. As in classical HHO methods, the present unfitted method introduces cell and face unknowns in uncut cells, but doubles the unknowns in the cut cells and on the cut faces. The main difference with classical HHO methods is that a Nitsche-type formulation is used to devise the local reconstruction operator. We prove stability estimates and optimal error estimates in the H1-norm. Robustness with respect to cuts is achieved by a local cell-agglomeration procedure taking full advantage of the fact that HHO methods support polyhedral meshes.