Scene flow estimation is a foundational task for many robotics applications, ranging from robust dynamic object detection to automatic labeling and sensor synchronization. Two distinct approaches to the problem have evolved: 1) Supervised and 2) optimization-based methods. While supervised methods are fast during inference and achieve high-quality results, they are limited by the need for large amounts of labeled training data and are susceptible to domain gaps. In contrast, unsupervised test-time optimization methods do not face the problem of domain gaps but usually suffer from substantial runtime or fail to converge to the right solution. Current optimization-based approaches often perform poorly on dynamic objects and mainly predict ego-motion. In this work, we mitigate several limitations of existing optimization-based methods. To this end, we 1) introduce a simple voxel grid-based model that exhibits advantageous characteristics compared to the standard MLP-based formulation and 2) introduce a new multi-frame loss formulation. We combine both contributions in our new method, termed Floxels. On our ego-motion compensated benchmark, based on nuScenes and Argoverse, Floxels achieves state of the art (SOTA) results and performs on par with a recently proposed SOTA supervised method. At the same time compute costs scale significantly more gracefully with point cloud size for Floxels, making it 3x faster than the previous fastest optimization based method for mid-sized point clouds.