There is growing evidence, based on both X-ray and radio observations of isolated neutron stars, that besides the large-scale (dipolar) magnetic field, which determines the pulsar spin-down behaviour, small-scale poloidal field components are present, which have surface strengths one to two orders of magnitude larger than the dipolar component. We argue in this paper that the Hall-effect can be an efficient process in producing such small-scale field structures just above the neutron star surface. It is shown that due to a Hall-drift induced instability, poloidal magnetic field structures can be generated from strong subsurface toroidal fields, which are the result of either a dynamo or a thermoelectric instability acting at early times of a neutron star's life. The geometrical structure of these small-scale surface anomalies of the magnetic field resembles that of some types of "star-spots". The magnetic field strength and the length-scales are comparable with values that can be derived from various observations.