Direct interaction between fiber lasers and a magnetic field is useful but seldom explored because fiber is known as magnetic field insensitive. In this Letter, the response of an erbium-doped dual-polarization fiber laser to a perpendicular gradient magnetic field is investigated. Measured as beat note frequency change, significant response greater than 500 MHz has been observed that is within theoretical expectation, and translates to a birefringence change of about 4×10-6 and a potentially very high response to a magnetic field of about 12.8 pT/Hz. The response can be further enhanced by increasing the gradient of the gradient magnetic field.