That depends on your definition of 'democracy', but the most often cited post-classical democracy we have definite proof of is in Iceland, which during the height of the medieval era was a republic under a parliament called the Althing.

Again, though, this depends on your definition of 'democracy'. Tribal confederations blur the line because, while most employ democratic rule, this rule is so vague and autonomous that some don't even consider them nations. The other issue with tribes is that we often have very little history about them prior to European exploration in the 15th and 16th centuries. The Igbo tribe in Nigeria, for example, consisted mainly of autonomous republics upon their first visit from Portugal but due to there being no written history of their people we can't know how many hundred/thousand years the Igbo have been following such a tradition.