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:
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:
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:
This hadith From Anas (R.A) which is recorded in Sahih Muslim is saying this:
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...
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...
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
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.