Reaching sub-millisecond 3D tracking of individual molecules in living cells would enable direct measurements of diffusion-limited macromolecular interactions under physiological conditions. Here, we present a 3D tracking principle that approaches the relevant regime. The method is based on the true excitation point spread function and cross-entropy minimization for position localization of moving fluorescent reporters. Tests on beads moving on a stage reaches 67 nm lateral and 109 nm axial precision with a time resolution of 0.84 ms at a photon count rate of 60 kHz; the measurements agree with the theoretical and simulated predictions. Our implementation also features a method for microsecond 3D PSF positioning and an estimator for diffusion analysis of tracking data. Finally, we successfully apply these methods to track the Trigger Factor protein in living bacterial cells. Overall, our results show that while it is possible to reach sub-millisecond live-cell single-molecule tracking, it is still hard to resolve state transitions based on diffusivity at this time scale.