The Parah Adumah was burned on top of Har Hamishchah, which is Har Hazeisim, the Mount of Olives. (The ashes of the Parah Adumah-red heifer were used to purify people from Tumas Meis.) This place was located directly to the east of the Beis Hamikdash, as learned from the Passuk (Bamidbar 19:4) "Elazar the kohen shall take some of its blood with his finger and sprinkle it directly towards (אל נוכח) the face of the Tent of Meeting seven times". From the words directly towards (אל נוכח) we learn that number one, he sprinkled the blood towards the entrance of the Kodesh Hakodoshim, and number two, that the location he was in must be directly opposite the Kodesh Hakodoshim. (The face of a building is the door, although from the fact that the passuk does not just simply say door, we learn that over here it also means the most important part of the Heichal, the Kodesh Hakodoshim. In order to see the entrance to the Kodesh Hakodoshim, however, you had to look through the door of the Kodesh. [Tosafos Chadashim, Parah 3:9])
Now, where on Har Hazeisim was the Parah Adumah burned? From the above-mentioned passuk, we learn that it was directly to the front of the Beis Hamikdash. From the Gemara in Yoma (16a) we see that this location was located along an axis that went from the door of the Heichal, through Sha'ar Nikanor, the gate of the Ezras Nashim, and Sha'ar Shushan, and until this point. From the Yerushalmi (Eiruvin 5:1) we know that the Beis Hamikdash was built directly on an exact east-west axis, making this place directly to the east of the Heichal. In Middos (2:4), the Mishnah states that the Kohen "stood on the top (בראש) of Har Hamishchah", indicating that the burning was done on the top of the mountain; however, it should be noted that in the manuscripts of the Mishnah, it does not say "on top".
The Radvaz, in his Peirush on the Rambam (Hilchos Beis Habechirah 6:5), asks, that in the Mishnah in Middos (2:4), it says that they had to make the eastern wall of Har Habayis shorter, so that the Kohen on Har Hazeisim could see the opening of the Heichal, because if it was the same height as the other walls, it would have blocked his view. However, the Radvaz asks, the top of Har Hazeisim is currently much higher than the Har Habayis, so he could look down over the walls, and easily see the door of the Heichal, even without making the wall shorter (see picture)! He answers with two answers. The first one is that it must not have been burned on the top of Har Hazeisim, but lower down on the hill. (It seems he had the manuscript version of the Mishnah, where it does not say that it was burned on the top.) The second one is that Har Habayis used to be much taller, as he explained in another place (שאלות ותשובות, סימן תרל"ט, see my article on this Teshuva here).
Another thing than can be learned from this Mishnah is that the location also had to be at the same elevation as the door of the Heichal. If it could have been lower, than he could have looked at an angle upward through the gates; and see through the door of the Kodesh without them having to lower the wall. Therefore, we must say that we learn that it must also be opposite it in height. (To see more about this idea, see R' Yoav Elan's blog post about this; Beis Hamikdash Topics: Elevation of the Kohen on the Mount of Olives.) Now, if the Har Habayis was taller than Har Hazeisim, as the Radvaz says, how can this be, there is no place that is on the same height level as the gate of the Kodesh? We must say that this was done by making the platform on which the Parah was burned reach this level, even though the natural ground doesn't.
Identification of this place during the times of the Rishonim
One of the people who visited Eretz Yisrael during the times of the Rishonim, and left us a detailed account of what he saw, was a student of the Ramban. He writes the following (see here for the original):
The Kaftor Vaferach also mentions the location of the burning of the Parah as a known place, and even says where on Har Hazeisim it was located, however his words are not so simple. He writes: "עוד היום מקובל המקום ההוא, והוא צפוני לקבר חולדה כמטחוי קשת שפל ממנו מעט-Until today this location is identified, it is north of Chuldah's grave, and slightly lower than it." This location is strange, as any location that is north of Chuldah's Kever is opposite the northern side of Har Habayis, while the Kaftor Vaferach clearly writes that Sha'ar Shushan, which was directly opposite the Beis Hamikdash, was to the south of Sha'ar Harachamim, making the Beis Hamikdash either in the southern side of Har Habayis, or in the center, and therefore the place of the Burning of the Parah has to be opposite this part of the Har Habayis. (See my article The Eastern Wall of the Har Habayis, part 3 (the gates in the middle of the eastern wall) for more on the Kaftor Vaferach's identification of Sha'ar Shushan, as well as his location of the Beis Hamikdash.)
R' Zalman Koren has also pointed out another interesting thing. (See his article in Kovetz Ma'alin Bakodesh, גיליון לא, pp. 102-105, it is also reprinted in the Sefer איה מקום כבודו, pp. 263-266.) The place identified as the grave of Chuldah is located pretty much directly to the east of Sha'ar Harachamim. Now, the Kaftor Vaferach writes that both Sha'ar Shushan and the location of the burning of the Parah are located the same exact distance (כמטחוי קשת-a arrowshot or two arrowshots) away from this axis of Sha'ar Harachamim and Kever Chuldah. Both of these two locations, Sha'ar Shushan and The Burning Place, are known from other sources to have been along the same axis. The only problem is that the Kaftor Vaferach says that one is on the northern side, and one is on the south. Because of all this, he says (taking after Avraham Luntz, in his edition of the Kaftor Vaferach,) that it seems there is a mistake in the Kaftor Vaferach, and it should really say that also The Burning Place was located south of Kever Chuldah. [This king of mistake is fairly common, and he shows in how it appears other times in the Kaftor Vaferach.] We could propose to change the description of Sha'ar Shushan to say it is in the north, but that would mean having to emend the Kaftor Vaferach twice, once when he says Sha'ar Shushan is located in the southern part of the wall, and also when he says that Sha'ar Harachamim is to the north of Sha'ar Shushan.
Now, where exactly is this location? Based on this Kaftor Vaferach, we should be looking around at the top of Har Hazeisim, at a distance of around 100 meters (which, based on other times the Kaftor Vaferach uses the expression of an arrowshot, especially the distance from Sha'ar Shushan to Sha'ar Harachamim, this seems to be the approximate size he wants to convey) from Chuldah's Kever. This area is directly opposite the dome of the rock, and the ground level here is slightly lower than by Chuldah's grave. Looking in this area, it appears that this location was in the area now occupied by the Pater Noster church. In the times of the Rishonim, this church did not exist, and there could have been a platform there. This fits even with the versions of the Mishnah (Middos 2:4) that say that this location was on the top of Har Hazeisim, as this obviously does not mean that it was located on the tippy top, but in the general area of the top of the mountain, where this place is indeed located. (The top of the mountain is 808 meters [2650 feet] above sea level, this place is 795 meters [2608 feet] above sea level.)
From the Mishnayos in Parah (chapter 3), as well as the commentaries on it, we get the following information about the platform on which the Parah was burned:
This whole platform, like the Kevesh leading to it from the Har Habayis, was built on arches, so that no tumah can rise up from underneath it. On this platform there was a mikveh, in which the Kohen burning the Parah immersed himself before doing the avodah. [Right before doing the Avodah, the elders of the Beis Din would make the Kohen tamei, and he would then have to immerse himself before doing the avodah. This was done as when someone immerses himself in a mikveh, he does not become fully tahor (in regard to Teruma and Korbanos) right away, but rather has to wait until nightfall. During this time period, he is called a tevul yom-someone who immersed that day. Now, the Chachamim have a tradition that in regard to the Parah Adumah, when the Passuk says it must be done by a pure man, it means even if he is a tevul yom, since in regard to Ma'aser Sheini, he is Tahor. The Tzedokim, however, who did not hold of the Torah Sheba'al Peh, said he must be completely tahor, and not even a Tevul Yom. In order to completely negate the Tzedoki opinion, the Chachamim would intentionally make the Kohen a tevul yom before he burned the Parah.]
On the platform there was a ditch, like a wine vat, in which the pyre was built. The pyre was made from cedar wood, laurel wood, boxwood, and smooth fig wood. (All the wood had to be smooth, but the other types are always smooth, so there is no need to mention it; fig wood, however, is sometimes smooth and sometimes not smooth, so the Mishnah [Parah 3:8] has to specify that we need smooth ones.) The pyre was set up in a pyramid shape, wider at the bottom and narrower at the top, as this made the fire concentrate on the Parah, located at its top. There were spaces ("windows") among the logs, this was done so the wind could travel between the logs and fan the flames, making the fire bigger. On the western side of the pyre, facing the Beis Hamikdash, was a large opening, in which the fire was placed to light the wood.
After the Parah was burned, its ashes were divided into three parts. One was put in the Cheil, next to the gate of the Ezras Nashim, one was kept on Har Hazeisim, and one was divided among all the Mishmaros (divisions) of Kohanim. These three parts were each used for a different purpose. The one in the Cheil was placed there as a safekeeping, like the Passuk (Bamidbar 19:9) says: וְהָיְתָה לַעֲדַת בְּנֵי־יִשְׂרָאֵל לְמִשְׁמֶרֶת-it shall be for a keepsake for the community of Bnei Yisroel. (These ashes were also used to purify the Kohen before he burned the Parah, see Parah 3:1) The one on Har Hamishchah was used by the Kohanim, and the one given out to all the Mishmaros was used by the Yisra'elim if they became tamei. (This is how our version of the Tosefta [Parah 3:8] explains the uses of the three parts. Rambam, however, seems to have had a different version of the Tosefta, as he writes [Hilchos Parah Adumah 3:4] that the one on Har Hamishchah was used by the Yisra'elim, and the one given out to the Mishmaros of Kohanim was used by the Kohanim.) I have made another room on the platform of the Parah, for storing the ashes that are to be kept on Har Hamishchah.
Rashi's opinion: two locations
The general opinion is that all the things done with the Parah: its slaughter, sprinkling its blood, and burning it, were all done at this same place, near the top of Har Hamishchah. Rashi, however, argues with this. From his words in Menachos (7b, ד"ה בשלמא, במאי מקנח), we see that he holds that the slaughtering and burning of it were done towards the bottom, of Har Hazeisim, and the Kohen would take the blood to the top of the mountain and sprinkle it there. Rabbeinu Shimshon (commentary to Parah 3:9) asks on Rashi from a Gemarah in Zevachim, which states that we learn out the slaughtering and burning of the Parah from the sprinkling, that they all have to be done opposite the Heichal. Tosafos, however, (Menachos 7b ד"ה אלא אצבעו במאי מקנח) answer this question; explaining that both of these locations were opposite the Beis Hamikdash, just one was higher up on the mountain, and one was lower. (It would seem from this that you only need the strict definition of opposite the opening, that it is also opposite in height, only by the actual sprinkling, where the passuk is written, and not by the slaughtering and burning, which are only learned out, but this seems kind of forced, and maybe this is Rabbeinu Shimshon's main question.)
[According to Rashi, you would need the Kevesh to continue, or there would be another Kevesh, going past the burning place, to the top of the mountain, as the Kohen who is doing the Parah also has to be protected from tumah on his way up to sprinkle the blood.]
The order of the Avodah of the Parah Adumah (from the Rambam, Hilchos Parah Adumah 3:2) [English translation Copyrighted by Moznaim Publications, used under a CC-BY-NC license]
I have added sixteen pictures of the third Beis Hamikdash, as well as a new map of it.
My name is Mendel Lewis.
Hashem said to Yechezkel, "Its reading in the Torah is as great as its building. Go and say it to them, and they will occupy themselves to read the form of it in the Torah. And in reward for its reading, that they occupy themselves to read about it, I count it for them as if they were occupied with the building of it. (Tanchuma tzav 14)