Multi-way data analysis is popular in chemometrics for the decomposition of, for example, spectroscopic or chromatographic higher-order tensor datasets. Parallel factor analysis (PARAFAC) and its extension, PARAFAC2, are extensively employed methods in chemometrics. Applications of PARAFAC2 for untargeted data analysis of hyphenated gas chromatography coupled with mass spectrometric detection (GC-MS) have proven to be very successful. This is attributable to the ability of PARAFAC2 to account for retention time shifts and shape changes in chromatographic elution profiles. Despite its usefulness, the most common implementations of PARAFAC2 are considered quite slow. Furthermore, it is difficult to apply constraints (e.g., non-negativity) to the shifted mode in PARAFAC2 models. Both aspects are addressed by a new shift-invariant tri-linearity (SIT) algorithm proposed in this paper. It is shown on simulated and real GC-MS data that the SIT algorithm is 20–60 times faster than the latest PARAFAC2-alternating least squares (ALS) implementation and the PARAFAC2-flexible coupling algorithm. Further, the SIT method allows the implementation of constraints in all modes. Trials on real-world data indicate that the SIT algorithm compares well with alternatives. The new SIT method achieves better factor resolution than the benchmark in some cases and tends to need fewer latent variables to extract the same chemical information. Although SIT is not capable of modeling shape changes in elution profiles, trials on real-world data indicate the great robustness of the method even in those cases.