Boolean matrix factorization aims to represent binary data as a product of two factor matrices, in order to uncover the underlying structure of the data and find a compressed representation. However, finding the factors of a given ground truth is computationally hard and calls for fast implementations that accomplish a good approximation in reasonable time. We present cuTeBool, a novel parallel algorithm that exploits Tensor Cores on CUDA-enabled GPUs for fast matrix operations based on a randomized approach. Our comprehensive performance evaluation shows that it produces approximate factorization competitive to other state-of-the-art tools within vastly reduced runtime for a variety of input matrices. Moreover, our algorithm is the only available method that scales well with the size of the ground truth and is able to factorize matrices that are at least one order-of-magnitude larger than all competitors. We further analyze algorithmic parameters allowing us to find a trade-off between performance and reconstruction quality.