We present an algorithm capable of performing fringe pattern phase demodulation from two frames with unknown, linearly nonuniform phase shift, i.e., under presence of the tilt-shift error. The method consists of intensity-based filtration of the tilt-shift component and subsequent two steps of a nonlinear error functional minimization. We verify the algorithm performance and robustness using both simulated and experimental data, indicating high accuracy of the presented method and its good numerical properties. Both small and large tilts can be treated. The Letter is complemented by numerical codes available online in Wielgus, "Two-frame tilt-shift error estimation and phase demodulation algorithm" (2015).