Although the concept of the existence of the atoms originates from the ancient Greek, for them it was yet more a philosophical concept, they were very far from any experimental proof.1
Later, mainly the chemistry provided the first suggestion that it might be an experimental fact.
However, none of these results was strong enough at the time. In the late XIX. century, it was still a common concept of mainstream science to accept the "atomic theory", but just as a practical approximation to calculate the possible mass ratios of the elements in their compounds, but without a real meaning. It was so mainly because the lack of experimental proofs.
The acceptance of the "atom theory" happened surprisingly late, at the late XIX, early XX. century, which was also the start of Einstein's work.
The important thing is: Perrin's result alone was not enough for it, it was accepted because many, essentially different, experiments determined the same Avogadro number. Probably Perrin was the first, but also Einstein provided one, using Brownian motion.2
Einstein's method worked by the statistical analysis of the Brownian motion of oil particles suspended in water. He measured the average distance of the drops due to their random Brownian motion in a microscope. It depends on the size of the atoms: if the atoms would be smaller, then the Brownian motion would be slower due to the better statistical leveling of the water molecules around the oil drops.
The experimental challenge was big: he had to find oil drops whose size is big enough to become visible in the microscope, but they are not big enough to make their Brownian motion invisible.
1Actually, they didn't really have experimental results. They were good at axiomatizing their theories, but practice and experiments weren't their strong side. Furthermore, science, math and philosophy didn't differ conceptually in their world view: this separation happened millennia later.
2As per this paper, he doesn't mention Brownian motion in his paper, although he had probably heard about it. His work is a "new method to calculate the mass of the molecules" (my translation).