My understanding is that the first source of the rhyme that wound its way into European poetry was Iranian (Persian) poetry. Persian poetry is notoriously complex and very heavy on rhyme, and poetry has long been and still is central to Persian culture (Hafiz's poems, for example, play a part in the New Year's celebration). The account that I've read (in Meg Bogin's excellent book The Women Troubadours) was that the Moors/Arabs learned rhymed from the Persians and then brought it into Spain; from there it moved into southern France via the troubadours, and eventually into English.