Now for starters, Fossil records have been, and remain (my opinion, as this is now becoming increasingly contested), the most convincing case in regard to evolution.

Well, after the DNA sequencing was done, some tweaking in phylogeny happened. For example, all anteaters were considered to originated only once because the teeth are very conservative. In other words, DNA sequencing is above the anatomy.

About the fossils:
We should keep in mind time he lived. Darvin died in 1882.
The first edition of "Origin of Species" was published in 1859.
The most iconic prehistoric animals that we found, Archeopteryx was discovered in 1861.

And that is where the power of his way of thinking is shining.
His theory provided the predictions what will be once found.