We solve the two-dimensional Stefan problem of solidification in a half-space, where the heat flux at the wall is a slightly varying function of position along the wall, by means of a large Stefan number approximation (which turns out to be equivalent to a small time solution), and then by means of the Heat Balance Integral Method, which is valid for all time, and which agrees with the large Stefan number solution for small times. A representative solution is given for a particular form of the heat flux perturbation.