Where was the first Qibla in Islam? Is there any verse in the Qur'an or hadith that established that Qibla? Why did Muslims pray towards Jerusalem?
What was the first Qibla in Islam?
The first Qibla Muslims prayed towards is Al-Aqsa mosque المسجد الأقصى (or Bait Al-Maqdis بيت المقدس), here is a lovely photo the southern "chapel" of it (which is the oldest and main part) :)
It's still a sacred place for Muslims (and Christianity and Judaism as well), in fact Allah blessed it and the lands surrounding it, and the Israa was from the Holy Mosque (Kaabah) to it, and the Miraj was from it to heaven see this aya, and it's there (in Al-Aqsa Mosque) where the Prophet prayed as Imam and all the Prophets behind them (Peace and Blessing Be Upon Them All).
Is there any verse or hadith that established that Qibla? Why Muslims prayed towards Jerusalem?
Yes, there is.
First to know is that the prophet prayed towards Al-Aqsa mosque before Hijrah, and after it, he prayed towards it for about seventeen months until Rajab of the second year (according to Ibn Abbas), when Allah ordered him to pray towards Kaabah.
Did the Prophet pray towards Al-Aqsa at the order of Allah or at his own decision?
The majority of scholars agreed that it was at the order of Allah, the following ayah is an evidence:
وَكَذَٰلِكَ جَعَلْنَاكُمْ أُمَّةً وَسَطًا لِّتَكُونُوا شُهَدَاءَ عَلَى النَّاسِ وَيَكُونَ الرَّسُولُ عَلَيْكُمْ شَهِيدًا ۗ وَمَا جَعَلْنَا الْقِبْلَةَ الَّتِي كُنتَ عَلَيْهَا إِلَّا لِنَعْلَمَ مَن يَتَّبِعُ الرَّسُولَ مِمَّن يَنقَلِبُ عَلَىٰ عَقِبَيْهِ ۚ وَإِن كَانَتْ لَكَبِيرَةً إِلَّا عَلَى الَّذِينَ هَدَى اللَّهُ ۗ وَمَا كَانَ اللَّهُ لِيُضِيعَ إِيمَانَكُمْ ۚ إِنَّ اللَّهَ بِالنَّاسِ لَرَءُوفٌ رَّحِيمٌ
And thus we have made you a just community that you will be witnesses over the people and the Messenger will be a witness over you. And We did not make the qiblah which you used to face except that We might make evident who would follow the Messenger from who would turn back on his heels. And indeed, it is difficult except for those whom Allah has guided. And never would Allah have caused you to lose your faith. Indeed Allah is, to the people, Kind and Merciful.
In this verse Allah says that he made the old qiblah (Al-Aqsa) for a reason (rest of the ayah), so this is an evidence that Allah is who chose Al-Aqsa as the first Qibla.
However, other scholars (the minority) say that he prayed towards it at his own decision, they say that although he did so, Allah wouldn't let him do that if he was wrong. Others say that he is preserved from mistaking.
However, even if it was at his own decision (although it wasn't), he used to pray towards Al-Aqsa through Kaabah. For after Hijrah, he probably chose it based on this ayah:
وَلِلَّهِ الْمَشْرِقُ وَالْمَغْرِبُ ۚ فَأَيْنَمَا تُوَلُّوا فَثَمَّ وَجْهُ اللَّهِ ۚ إِنَّ اللَّهَ وَاسِعٌ عَلِيمٌ
And to Allah belongs the east and the west. So wherever you [might] turn, there is the Face of Allah . Indeed, Allah is all-Encompassing and Knowing.
A final note before leaving: the photo below show the complete Al-Aqsa mosque, the green area is the entire Al-Aqsa mosque, eveything within the wall. The main and original and oldest building is the one to the south-left corner of the photo (also shown in the photo above in the answer), it's considered the Al-Aqsa mosque infact. While the golden dome in the center is called "The Rock Dome قبة الصخرة", built by Khalifah Omar Ibn Al-Khattab (may Allah be pleased with him) when he entered the city.
The First Qibla of Islam was toward Bitul-Maqdis, which is now in Jerusalem. Muslims used to pray Salat towards this Qibla, until this Ayat is revealed:
We have certainly seen the turning of your face, [O Muhammad], toward the heaven, and We will surely turn you to a qiblah with which you will be pleased. So turn your face toward al-Masjid al-Haram. And wherever you [believers] are, turn your faces toward it [in prayer]. Indeed, those who have been given the Scripture well know that it is the truth from their Lord. And Allah is not unaware of what they do 1
This hadith From Anas (R.A) which is recorded in Sahih Muslim is saying this:
Anas reported: The Messenger of Allah (may peace be upon him) used to pray towards Bait-ul-Maqdis, that it was revealed (to him):" Indeed We see the turning of the face to heaven, wherefore We shall assuredly cause thee to turn towards Qibla which shall please thee. So turn thy face towards the sacred Mosque (Ka'ba)" (ii. 144). A person from Banu Salama was going; (he found the people) in ruk'u (while) praying the dawn prayer and they had said one rak'ah. He said in a loud voice: Listen! the Qibla has been changed and they turned towards (the new) Qibla (Ka'ba) in that very state. 2
Before the Qur'an came from Allah the Bible (new & old testament) came from Allah . According to the old testament people were required to pray towards Jerusalem.
The origin of this is based in the Bible as below...
"If thy people go out to battle against their enemy, whithersoever thou shalt send them, and shall pray unto the LORD toward the city ( Jerusalem ) which thou hast chosen, and toward the house ( Baitul Makdas ) that I have built for thy name" [ 1 Kings 8:44 ]
So Muslims were following that direction because that was the last known direction of prayer given by Allah until He changed it in the Quran towards Mecca based on the verse below...
"From whencesoever Thou startest forth, turn Thy face in the direction of the sacred Mosque; that is indeed the truth from the Lord. And Allah is not unmindful of what ye do." [Qur'an 2:149]
Answering my self for lack of complete answer
The first Qiblah of Islam is unknown to the best of my research. Although by most people it is believed to be Bait-ul-Muqadas in Jerusalem.
We can certainly say that when the prophet was in Medina, he faced toward Jerusalem for Qibla direction. This is verified from the following haidiths Volume 1, Book 8, Number 392
Allah's Apostle prayed facing Baitul-Maqdis for sixteen or seventeen months but he loved to face the Ka'ba (at Mecca) so Allah revealed: "Verily, We have seen the turning of your face to the heaven!" (2:144) So the Prophet faced the Ka'ba and the fools amongst the people namely "the Jews" said, "What has turned them from their Qibla (Bait-ul-Maqdis) which they formerly observed"" (Allah revealed): "Say: 'To Allah belongs the East and the West. He guides whom he will to a straight path'." (2:142) A man prayed with the Prophet (facing the Ka'ba) and went out. He saw some of the Ansar praying the 'Asr prayer with their faces towards Bait-ul-Maqdis, he said, "I bear witness that I prayed with Allah's Apostle facing the Ka'ba." So all the people turned their faces towards the Ka'ba.
Note that it says for 16 or 17 months (not 13 years or so when Islam was propagated). This was the second year of the prophet in Madina (2nd Hiji). This would mean the Masj-al-Aqsa qibla was specifically made Qibla in Madina after the prophet migrated.
Verse says 2:143
And We did not make the qiblah which you used to face except that We might make evident who would follow the Messenger from who would turn back on his heels.
This proves that the Bait-ul-Muqaddas Qibla was not ordered by God as God says "We did not make that Qibla" and "test who would follow the prophet" because the prophet ordered (not through divine intervention though, because it was a test). Most likely the prophet ordered it after the Migration to Madina. This would certify that it was actually a test. However interestingly no reference to this event exists in any hadith.
History: The prophet did it most likely to please the Jews. There are hadith available that mentions the prophets fasted on the 10th of Muhammad when Jews told them it is auspicious day because of Moses. The prophet order Muslim to fast on that day to for "we have more right over Moses"(Sahih al-Bukhari, Volume 3, Book 31). Making Juraselam as Qibla was probably one such provision that the prophet made.
In short Bait-ul-Muqadas was not likely the first Qiba of Islam but it was adopted in Madina, then later changed to Kabba. We still do not know for sure what was the first Qibla in Islam.
Masjid e Aqsa was never build by any one before prophet Muhammad (saww) it does not even exist. the only thing was in Jerusalem was Hakel e Solamani (which lots of muslim called bait ul muqadas) which was Sacred place for jews not for christens not for even people of makkah. it was destroyed in 500 years before prophet Muhammad (saww) birth and romans completely destroyed Hakl e soulamani, the only thing was left there runes of Hakl e soulamani. chritren has made it garbage dump. (there was nothing there and no masjid aqsa or any msjid was build at that place then to which direction prophet Muhammad was actually prying) romans never alowed jews to come to there holy place. Jerusalem was under control of romns until Muslims conquer it in the leader ship of Hazrat Omer. its was Hazrat Omer who allowed jews to come to their holy place. and next to Hal e solamni he bulid Masjid which was named Aqsa coz Aqsa mean far away Masjid. Jerusalem was never qibla for any one who lives in Makkah. its just a myth created by Jews.
The first house of worship on this Earth was at Mecca/Bekka. The first Qibla must be the same thing, since there was no other worshipping place on the Earth. The Holy Qur'an did not say that the first Qibla was somewhere else.