We construct a space-time conservation element and solution element (CESE) scheme for solving the compressible Euler equations on moving meshes (CESE-MM) which allow an arbitrary motion for each of the mesh points. The scheme is a direct extension of a purely Eulerian CESE scheme that was previously implemented on hybrid unstructured meshes (Shen et al., J. Comput. Phys., 2015). It adopts a staggered mesh in space and time such that the physical variables are continuous across the interfaces of the adjacent space-time control volumes and, therefore, a Riemann solver is not required to calculate interface fluxes or the node velocities. Moreover, the staggered mesh can significantly alleviate mesh tangles so that the time step can be kept at an acceptable level without using any rezoning operation. The discretization of the integral space-time conservation law is completely based on the physical space-time control volume, thereby satisfying the physical and geometrical conservation laws. Plenty of numerical examples are carried out to validate the accuracy and robustness of the CESE-MM scheme.