In the early 20th century, in the heyday of discovering planets by observing existing planets and realizing that classical mechanics didn't quite predict their orbits correctly, it was observed that Mercury's orbit didn't fit the classical model well enough. Reasonably enough, it was presumed that there was another planet orbiting inside of Mercury's orbit. This planet was dubbed "Vulcan", and the fact that no one had ever observed Vulcan was explained away by the fact that it was clearly too close to the sun to be observed. This was all well and good until the early heyday of Einstein's theories, which made small but crucial changes to the mathematical models of classical mechanics. The orbit of Mercury was found to be perfectly consistent with Einstein's model.
The question of dark matter supposes a dichotomy: either our current understanding of physics is essentially accurate and there's a ton of fundamentally unobservable matter in the universe that explains any anomalous observations, or our model of physics isn't quite right yet. Intuitively, I think it's more likely our physics are off.