He is credited with discovering natural selection not evolution. The two are often confused and he is associated with evolution.

Natural selection is how most animals came to be. Animal breeders also do selection, unnatural or artificial selection, but the process is still evolution. People definitely thought animals change, they even changed animals themselves. But the detailed understanding of how and why they changed is what Darwin discovered. Like you say this took a lot of work and insight.

People had ideas and hypothesis, but no theory till Darwin.