Whilst in one sense you just have to accept it because of the evidence, but it does naturally follow from the assumption that the laws of physics are the same for all observers (in "inertial" ie freely falling frames at any rate). The only way you can get any sensible results in electromagnetism is to accept the constancy of the speed of light. Einstein's leap was to give up the Newtonian view in order to make Maxwell's equations work. In a sense it's easier to accept one counter intuitive thing rather than have the rest of physics collapse in a heap
Others like Lorentz were nearly there already, and Maxwell himself maybe had it within reach -he was certainly clever enough but I guess his own predictions were not sufficiently established for him to make the next step.