John Norton at Pitt relates the story quite nicely.
In Einstein's own words:
After ten years of reflection such a principle resulted from a paradox
upon which I had already hit at the age of sixteen: If I pursue a beam
of light with a velocity c (velocity of light in a vacuum), I should
observe such a beam of light as a spatially oscillatory
electromagnetic field at rest. However, there seems to be no such
thing. . . on the basis of experience. . . . From the very beginning
it appeared to me intuitively clear that, judged from the standpoint
of such an observer, everything would have to happen according to the
same laws as for an observer who, relative to the earth, was at rest.
For how, otherwise, should the first observer know, that is, be able
to determine, that he is in a state of fast uniform motion?
In other words, assuming both
(1) that all motion is relative and
(2) that it's possible for an observer to travel at $C$
leads to an impossibility:
(3) that there is a reference frame in which a beam of light is just a "spatially oscillatory electromagnetic field at rest" i.e, a motionless electromagnetic wave.
Since he judged (3) to be impossible, then either (1) or (2) or both must be wrong. His insight was that (2) is wrong, that the speed of light is not attainable.