A method for performing nonlinearity calibration includes the steps of: obtaining temporarily values of a plurality of compensation parameters by performing a perturbation-based calibration process on a nonlinear system with at least one predetermined input being applied to the nonlinear system; and updating the compensation parameters by performing the perturbation-based calibration process in an online manner, wherein the temporarily values are utilized as initial values of the compensation parameters for the step of updating the compensation parameters. In addition, the compensation parameters are utilized for controlling a compensation response of the perturbation-based calibration process. An associated apparatus is also provided.