Combination of factors. Revolving around a very small parasite
I propose a sequence of events consisting of a drought combined with a pandemic followed by a severe parasitical infection with a flying vector together with a climate change so it spreads to all of the horse's habitat.
Extinction usually is caused by a combination of factors; first the species is decimated and once in decline with a smaller habitat and reduced viability of individual specimen it soon enters that critical stage where it takes little to finish the species off.
Starting point
Let's assume horses are domesticated and have spread to all continents, to start. Humanity travels, has colonized, but still lacks thorough understanding of the causes of diseases and how they spread.
Setting the stage
Every once in a while due to for example changing weather patterns from el Nino a drought occurs. If this draught is severe enough and coincides with a pandemic of a newly introduced and so especially virulent cattle disease it it can depopulate a fairly large region. Once the stage is set the fields become overgrown with wild bushes providing a hiding place for a disease carrying fly. This population explodes making the area totally unsuitable for horses, killing them off, and badly suited for all other livestock permanently crippling the ability to support mixed farming and thus any population at all.
This gets you a staging area from which to kill off the rest of the horses world-wide.
How to eliminate any escape
Now enter some clueless travelling people and changing (warming?) weather patterns.
People don't like this turn of events and the survivors flee the area. They take with them all they can carry, and all that can walk. So the surviving but increasingly sick livestock carrying the parasites and the flies come along nicely. They flee as far as they can towards all the corners of the known world and maybe discover a bit more along the way.
This scenario works with everything bigger than a caravel up to steam boats and spreads the problem to all continents.
Next have some horses escape, bringing just a few infected flies with them to contaminate the local horses. Due to unseasonal (warm?) weather the vector survives killing off most specimen eventually. The remainder becomes smaller, weaker, rarer and has trouble to breed. Give or take some few decades and the last survivors succumb.
All you need for this is the flies being present in sufficient numbers across all of the horse's habitat.
Background
Sounds far-fetched? Wel... Even today a large part of Africa is void of livestock due to nagana (a sleeping sickness variety spread by the tse tse fly). Horses are particularly susceptible. This came about after a drought that concurred with the introduction of rinderpest to the continent, causing the African big game preserves we all know today. Throw in a bit of Australian rabbit husbandry and extrapolate the horse's extinction in North America and you are almost there already.
References:
https://en.wikipedia.org/wiki/Tsetse_fly
http://www.who.int/trypanosomiasis_african/country/history/en/
https://www.alternatehistory.com/forum/threads/sleeping-sickness-resistant-horse-breeds.383852/
http://horseflynet.com/blog/?p=351