Reconciling between the verses “There is no compulsion in religion” [al-Baqarah 2:256] and “and we shall drive them out from there in disgrace, and they will be abased” [an-Naml 27:37]
Question

Allah, may He be exalted, says in Soorat al-Baqarah: “There is no compulsion in religion” [al-Baqarah 2:256], and this is a well-known Islamic principle. But in Soorat an-Naml we find that the Prophet of Allah Sulaymaan (peace be upon him) sent a message to Bilqees threatening her and compelling her to become Muslim. It seems to me that this is contrary to the general principle. How can you explain this?
Praise be to Allah.Firstly: 
The words of Allah, may He be exalted (interpretation of the meaning): “There is no compulsion in religion. Verily, the Right Path has become distinct from the wrong path” [al-Baqrah 2:256] are not contrary to the command to fight the mushrikeen who turn people away from the religion of Allah, cause mischief on earth and spread kufr, shirk and corruption. Fighting them is one of the greatest deeds by means of which people prosper on earth and enjoy safety and stability, as Allah, may He be exalted, says (interpretation of the meaning): “And fight them until there is no more Fitnah (disbelief and polytheism: i.e. worshipping others besides Allah) and the religion (worship) will all be for Allah Alone” [al-Anfaal 8:39]. 
Islam aims to achieve that which is in people’s interests and to protect them from that which is harmful to them. 
The meaning of this verse is that the teachings of Islam are very clear and the proof and evidence of its soundness are so clear and definitive that there is no need for compulsion. Whoever comes to know the reality of Islam and is not stubborn or arrogant will enter Islam willingly. Rather the one who does not want to enter it is the one who is arrogant and stubborn, who does not accept Allah as his Lord or His Prophet as his messenger, and does not believe in the Book that was revealed to him. For that reason, those mushrikeen who adhere to their false religion and fight in support of their religion out of arrogance and seek to spread mischief and kufr on earth are to be fought. 
Nothing is more indicative of that than the fact that at the beginning of Islam people entered the religion of Allah in crowds, the religion in the name of which their fathers, relatives and friends had been killed. 
Many of the Sahaabah became Muslim after having fought to defend kufr, such as Khaalid ibn al-Waleed, ‘Amr ibn al-‘Aas, Abu Sufyaan ibn Harb, Mu‘aawiyah ibn Abi Sufyaan and many others (may Allah be pleased with them all). They became Muslim when the right path became distinct from the wrong path for them and the teachings and strong proof of Islam became clear to them. So they became Muslim willingly and joined the troops of Allah after having been among the troops of the Shaytaan. 
This is also indicated by the verse in which Allah, may He be exalted, says (interpretation of the meaning): “And had your Lord willed, those on earth would have believed, all of them together. So, will you (O Muhammad SAW) then compel mankind, until they become believers?” [Yoonus 10:99]. In other words, you are not able to do that and it is not within your power; no one except Allah is able to do any of that.
End quote from Tafseer as-Sa‘di, p. 374 
Ibn Jizziy (may Allah have mercy on him) said: “There is no compulsion in religion” means: the religion of Islam is very clear and its proof of its soundness is self-evident, so there is no need to compel anyone to enter this religion. Rather anyone who has sound understanding will enter it of his own accord, without compulsion. This is indicated by the words, “Verily, the Right Path has become distinct from the wrong path” [al -Baqarah 2:256], i.e., it is clear that Islam is the right path and kufr is the wrong path, so there is no need for compulsion after this has become clear.
End quote from at-Tasheel, p. 135 
As-Sa‘di (may Allah have mercy on him) said: 
This refers to the perfection of Islam, because its proofs are perfect and the signs of its soundness are clear. Because it is the religion of reason and knowledge, the religion of sound human nature and of wisdom, the religion of righteousness and piety, the religion of truth and guidance, and it is perfect and acceptable to human nature, there is no need to compel anyone to enter it, because compulsion is only needed in the case of that which is off-putting and contrary to the facts and truth, or that of which the proofs and signs are not clear. Otherwise, anyone who comes to know this religion then rejects it and does not accept it, it is because of his stubbornness, because right path has become distinct from the wrong path, so no one has any excuse for rejecting it and not accepting it. There is no contradiction between this idea and the many verses that speak of jihad. Allah enjoined fighting so that the religion (worship) will all be for Allah alone and to ward off the aggression of those who are hostile towards Islam. The Muslims are unanimously agreed that jihad is ongoing and that jihad in word and in deed is a permanent obligation. Any commentator who thinks that this verse contradicts the verses of jihad, and is certain that it has been abrogated, holds a weak view, as is obvious from the wording and the meaning and as is clear to anyone who studies the verse, as we have pointed out.
End quote from Tafseer as-Sa‘di, p. 954 
He also said: 
“Verily, the Right Path has become distinct from the wrong path” [al-Baqarah 2:256] means: once the one becomes distinct from the other, there is no room for compulsion, because compulsion can only be in the case of an issue the soundness and merits of which are not clear. But once it is clear that well-being and happiness in this world and in the Hereafter are connected to it, then what reason can there be for compulsion? 
Something similar may be said concerning the verse (interpretation of the meaning): “And say: ‘The truth is from your Lord.’ Then whosoever wills, let him believe, and whosoever wills, let him disbelieve” [al-Kahf 18:29]., i.e., this is the truth that clear evidence demonstrates is true, so that whoever wants to believe may do so and let whoever wants to disbelieve may do so.
End quote from al-Qawaa‘id al-Hisaan, p. 119 
Az-Zarqaani (may Allah have mercy on him) said: 
With regard to the sword and the concept of jihad in Islam, that was not for the purpose of imposing belief on people or forcing any individual or group to worship Allah; rather it was to ward off those who would wield the sword, to prevent them from humiliating and persecuting the one who entered Islam, and to compel them to leave the call of truth alone without any obstacle or hindrance, so that there will be no more titnah  and the religion (worship) will all be for Allah Alone (cf. 8:39). 
End quote from Manaahil al-‘Irfaan, 2/406 
Some of the scholars are of the view that this verse applies specifically to the People of the Book and those who come under the same rulings, such as the Magians; they are not to be compelled to enter Islam, because Allah, may He be exalted, says: “Fight against those who believe not in Allah, nor in the Last Day, nor forbid that which has been forbidden by Allah and His Messenger and those who acknowledge not the religion of truth (i.e. Islam) among the people of the Scripture (Jews and Christians), until they pay the Jizyah with willing submission, and feel themselves subdued” [at-Tawbah 9:29]. 
Ibn Qudaamah (may Allah have mercy on him) said: 
If one whom it is not permissible to compel is compelled to enter Islam, such as a dhimmi (non-Muslim living under Muslim rule) or a non-Muslim who has been granted security, he is not deemed to be a Muslim unless he shows signs of having become Muslim voluntarily.
End quote from al-Mughni, 10/96. 
Shaykh al-Islam Ibn Taymiyah (may Allah have mercy on him) said: 
The disbelief of one who is compelled to leave Islam is not to be regarded as anything significant and neither is the faith of one who is compelled unlawfully to believe, such as the dhimmi who is complying with the conditions (of being protected by the Muslim state and so on), as Allah, may He be exalted, says concerning him: “There is no compulsion in religion. Verily, the Right Path has become distinct from the wrong path” [al-Baqrah 2:256]. This is unlike the one who is compelled (to enter Islam) for a legitimate reason, such as those who were fought of people who are in a state of war with the Muslims, until they become Muslim, if the fight against them was to make them choose between becoming Muslim or paying the jizyah.
End quote from al-Istiqaamah, 2/320 
See also the answer to question no. 165408
The point is that the verse does not mean that people should be compelled to enter the religion of Allah reluctantly and by force; rather what it means is that Islam is easy and clear, with no compulsion to enter it. The one who enters Islam becomes one of its people, and the one who does not enter Islam is either one of the ahl adh-dimmah or one of those who have a covenant with the Muslims; he is to be granted his rights to safety and security and he has to pay the jizyah, or he is one of those who are in a state of war with the Muslims and must be fought lest he spread corruption and kufr in the land. 
Secondly: 
The words of Allah, may He be exalted, to His Prophet Sulaymaan (peace be upon him): “Go back to them. We verily shall come to them with hosts that they cannot resist, and we shall drive them out from there in disgrace, and they will be abased” [an-Naml 27:37], do not contradict what we have said above. The Prophet of Allah Sulaymaan (peace be upon him) had gained control over the land, as Mujaahid (may Allah have mercy on him) said: Four people gained control over the earth, east and west, two believers and two disbelievers. The two believers were Sulaymaan ibn Dawood and Dhu’l-Qarnayn, and the two disbelievers were Nebuchadnezzar and Nimrood ibn Kan‘aan (Nimrod son of Canaan). No one but they gained power over it.
Tafseer at-Tabari, 5/433 
The king must be obeyed, especially if he issues commands that are in the people’s interests and are good for the people and the country, such as believing in Allah and shunning kufr. So it is not permissible for anyone to go against him in that regard, and whoever does go against him must be fought, because he may cause trouble in the kingdom and spread kufr and corruption in the land, and others may follow him in that. 
Moreover, there is nothing in the verse to suggest that he compelled the queen, Bilqees, or anyone else to become Muslim. Rather what it refers to is fighting her and her army. In fact she became Muslim voluntarily, because of what she saw of the great signs that Allah granted at Sulaymaan’s hands; it was not because of fear of fighting and the sword. Allah, may He be exalted, tells us (interpretation of the meaning): “She said: ‘My Lord! Verily, I have wronged myself, and I submit (in Islam, together with Sulaymaan (Solomon), to Allah, the Lord of the ‘Aalameen (mankind, jinns and all that exists)’” [an-Naml 27:44]. 
From the above it is known that the command to fight does not mean compelling people to become Muslim. 
Thirdly: 
If we assume that this story refers to Sulaymaan (peace be upon him) compelling the Queen of Saba’ (Sheba) and the people with her to accept his laws that Allah sent down to him, this has to do only with the laws of Sulaymaan (peace be upon him), which were different to our laws. Allah, may He be exalted, says (interpretation of the meaning): “To each among you, We have prescribed a law and a clear way” [al-Maa’idah 5:4]. 
As-Sa‘di (may Allah have mercy on him) said: These laws, that were different for different nations, are what changed according to changes in times and circumstances. All of them were aimed at achieving justice at the time when they were prescribed.
Emd quote from Tafseer as-Sa‘di, p. 234 
Moreover, this ruling, which allows the dhimmi to continue following his religion and to be granted protection by the Muslims, and does not require compelling him to enter the religion of Allah, will change at the end of time, when ‘Eesa (Jesus – peace be upon him) comes down. He will abolish the jizyah and will not accept anything but Islam, and there will be a great deal of good and blessing throughout the earth. This is one of the things which indicate that fighting the mushrikeen who turn people away from the religion of Allah is one of the greatest means of bringing goodness and blessings to the people, common folk and elite alike. 
Al-Bukhaari (2222) and Muslim (155) narrated that Abu Hurayrah (may Allah be pleased with him) said: The Messenger of Allah (blessings and peace of Allah be upon him) said: “By the One in Whose hand is my soul, soon the son of Maryam will descend among you as a just judge, he will break the cross, kill the pigs and abolish the jizyah, and wealth will become so abundant that no one will accept it.” 
An-Nawawi (may Allah have mercy on him) said:
With regard to the words of the Prophet (blessings and peace of Allah be upon him), “and (he will) abolish the jizyah”, the correct view concerning their meaning is that he will not accept it, and he will not accept anything from the kuffaar except Islam. He will not leave alone those who are willing to pay the jizyah, because it will not be good enough; rather he will not accept anything except Islam or execution. This is the view of Abu Sulaymaan al-Khattaabi and other scholars, may Allah have mercy on them. 
Based on that, it may be asked: Will this be different from the Islamic ruling that exists today, which is that if the kitaabi (Jew or Christian living under Muslim rule) pays the jizyah, it must be accepted and it is not permissible to fight him or compel him to become Muslim? 
The answer to that is that this ruling is not ongoing until the Day of Resurrection; rather it is limited to the time before ‘Eesa (peace be upon him) comes down. The Prophet (blessings and peace of Allah be upon him) has told us in these saheeh hadeeths that it will be abrogated. But ‘Eesa (peace be upon him) is not the one who will abrogate it; rather it is our Prophet (blessings and peace of Allah be upon him) who explained that it will be abrogated. ‘Eesa will rule in accordance with our sharee‘ah, which indicates that his refusal to accept the jizyah at that time is what is prescribed by our Prophet Muhammad (blessings and peace of Allah be upon him).
End quote. 
See also the answer to question no. 34770
And Allah knows best.