Recently, a variable step-size affine projection (VSS-AP) algorithm has been introduced. The algorithm provides faster convergence rate and lower misadjustment but has heavy computational complexity. Proposed is a new variable step-size pseudo affine projection (VSS-PAP) algorithm, which not only has a much lower complexity than the VSS-AP algorithm but also provides performance comparable with the conventional algorithm. Simulation results confirm fast convergence rate and small misalignment of the proposed algorithm with less computational complexity.