It was found on April 20th, 1904, by Max Wolf in Heidelberg, and initially catalogued as 1904 NY. Where its name came from is not known; it may be named after the mythical Hercules, or after an unknown woman of that name. Most of the asteroids found by Wolf around this date were named for characters in operas, but if this name was also drawn from such a source, no explanation has been recorded.
Herculina is one of the twenty or so biggest members of the main asteroid belt.
It has often been noted for its complex lightcurves, which made finding its shape and rotation somewhat hard. A set of 1982 speckle inferometry observations led to a simple preliminary model of Herculina as a three-axis object, perhaps 260 by 220 by 215 km. 1985 analysis of this data concluded there was a nonspherical shape with one bright spot, whilst a 1987 photometric astrometry study concluded the object was spherical with two dark spots (and rotated around a completely different pole), which was in turn negated by a 1988 thermal study which showed the object could not be spherical. By the late 1980s, the generally accepted model was a three-axis object with major albedo or topographical features.
Recent (2002) modelling of photometric data shows that Herculina is not spherical, but a blocky shape not unlike a battered cuboid - or, as the analysis described it, it "resembles a toaster". This analysis indicates the presence of many big craters, similar to 253 Mathilde, but no major changes in albedo. The approximate ratios of the axes were suggested as 1:1.1:1.3, broadly consistent with earlier models if a bit more stretched.
Following anomalous sightings during an occultation of the star SAO 1220774 in 1978, Herculina became the first asteroid to be "confirmed" to have an asteroid moon, with the parent asteroid estimated at a 216 km diameter and a moon of about 45 km orbiting at a distance of around 1,000 km. However, careful studying in 1993, using the Hubble Space Telescope, could not locate a moon.