The point spread function (PSF) of single molecule emitters can be engineered in the Fourier plane to encode three-dimensional localization information, creating double-helix, saddle-point or tetra-pod PSFs. Here, we describe and assess adaptations of the phasor-based single-molecule localization microscopy (pSMLM) algorithm to localize single molecules using these PSFs with sub-pixel accuracy. For double-helix, pSMLM identifies the two individual lobes and uses their relative rotation for obtaining z-resolved localizations, while for saddle-point or tetra-pod, a novel phasor-based deconvolution approach is used. The pSMLM software package delivers similar precision and recall rates to the best-in-class software package (SMAP) at signal-to-noise ratios typical for organic fluorophores. pSMLM substantially improves the localization rate by a factor of 2 – 4x on a standard CPU, with 1-1.5·104 (double-helix) or 2.5·105 (saddle-point/tetra-pod) localizations/second.