At my TKD school, it's a minimum of 2.5 years to get your black belt. It takes 12 tests to get your black belt, and we have tests every 2 months. Up until Red belt you can test every time, but to get Red I, Red II, and then black belt there's a minimum 4 month waiting period*. So 9 tests at 2 months each and 3 tests at 4 months each, and you can potentially have your black belt in 30 months. Of course, we have black belt tests only twice a year, so that could be 34 months depending on your timing.
*This is all, of course, barring special permission from the Master. He will sometimes accelerate students who have prior martial arts experience, and sometimes if a student will be moving he will allow them to take additional classes to bump them up a bit before they go.
However, that timing is only if you test every time. Most students do not test every testing period. It's very common that a student will add at least 2 months to every test, which makes it a 4.5 year journey to black belt. We have another student who started a bit before me and tested for yellow belt with me. He might test for his black belt when I test for my 3rd Dan.
In my case, it took me 23 months to get to black belt. After 1 year at the school, my Master gave me the opportunity to do an instructor internship to learn how to be an instructor. This was in part because he needed an instructor, in part because I had prior martial arts experience (4 years in TKD when I was a kid, but I started over as a white belt at his school), and in part because I had no life so I was available to teach. I was at the dojang, either helping with or taking classes, for 20 hours a week. I think that helped entitle me to a bit of a faster progression.