In the early 1210s, Andrew sent "an army of Saxons, Vlachs, Székelys and Pechenegs" commanded by Joachim, Count of Hermannstadt, (now Sibiu, Romania) to assist Boril of Bulgaria's fight against three rebellious Cuman chieftains.

Andrew's army defeated the Cumans at Vidin. Andrew granted the Barcaság (now Țara Bârsei, Romania) to the Teutonic Knights. The Knights were to defend the easternmost regions of the Kingdom of Hungary against the Cumans and encourage their conversion to Catholicism.