Khmelnytsky started looking for another foreign ally. Although the Cossacks had established their "de facto" independence from Poland, the new state needed legitimacy, which could be provided by a foreign monarch. In search of a protectorate, Khmelnytsky approached the Ottoman sultan in 1651, and formal embassies were exchanged. The Turks offered vassalship, like their other arrangements with contemporary Crimea, Moldavia and Wallachia. However, the idea of a union with the Muslim monarch was not acceptable to the general populace and most Cossacks.