Matthew is almost unanimously testified as the oldest gospel by the church fathers. Clement of Alexandria even supported both Matthew and Luke as before Mark. This is significant because Mark is said to have founded the Coptic branch of Christianity in Alexandria, Egypt. If any place were to argue for Markan priority, Egypt would be the most likely. A sampling of the church fathers' testimony follows:
- Papyus “Matthew wrote in Hebrew and others translated.”
- Origen said the first gospel was written by Matthew in Hebrew.
- Iraneus (grandson in the faith of John by Polycarp of Smyrna) said the first gospel was written written by Matthew in land of Hebrews in their own language.
- Eusebias — Matthew had first preached to Hebrews and wrote in their own language
- Jerome “Matthew was the first to compose in Hebrew and his text is still available in [library near Bethlehem].” He even challenged his critics to go see it if they doubted.
As the church rose out of the mission to the gentiles, it is interesting that the church fathers supported the Judaic gospel of Matthew instead of Mark. Also consider that they testify that Mark was the companion of the Apostle Peter in Rome which became one of the five sees of the early church (Rome, Constantinople, Antioch, Jerusalem, and Alexandria, Egypt). Unless the tradition of Matthean priority were very early, it is unlikely that they would all arrive at it independently. In fact, the slight differences in their testimonies provide evidence that they came from different sources.
Even though one of the main arguments for Markan priority is that Mark is shorter and "later authors would be more likely to expand than contract," such is not always the case (see, for example, the Reader's Digest Condensced Library). Summarizing a longer work is well known and has been for a long time. There are even ancient works which name their sources and state, "this work will be a shorter, more understandable account of the events than X."
The Didache clearly relies on Matthew. While the date of this document is debated between AD 50 and AD 150, the earlier it is, the earlier Matthew has to be.
When you examine second-century Christian writings, Matthew is quoted far more frequently than Mark. So is Luke. If Mark enjoyed a period when it was the only written gospel, it seems that it should have been more popular. Likewise, Matthew's Gospel enjoys a more central place in the second century liturgy than any other gospel or even Paul's epistles.
I am separating textual evidence from internal evidence. The difference is that internal evidence will be themes or concepts while textual evidence deals with specific words and phrases.
The fall of Jerusalem is completely missing from Matthew. This event rocked the Jewish world. Matthew, who so often points out when a prophecy is fulfilled, does not add an editorial comment to Jesus' prophecy that Jerusalem would be overthrown. Not a single "and this prophecy was fulfilled" about the fall.
[added on edit]
Some have pointed to Matthew 22:7 as referring to the fall of Jerusalem as an event happening in the past. In fact, this verse is almost universally accepted as such. However, sending in troops and burning a city with fire were quite common ways of dealing with troublesome cities in the past. In fact, it is so common in Near Eastern, Old Testament, and Rabbinic writings that its occurrence here should not be thought to refer to a single event.
Moreover, for an after-the-fact prophecy, Matt 22:7 is very inexact. While the walls of Jerusalem fell, it was the temple that burned. In fact, post event "prophecies" do make this distinction.
We have overthrown the wall of Zion and we have burnt the place of the mighty God (II Baruch 7.1). [I.e. the temple. For this sense, cf. II Mace. 5.17-20; John 11.48; Acts6.14; 21.28; etc.]
They delivered ... to the enemy the overthrown wall, and plundered the house, and burnt the temple (II Baruch 80.3).
And a Roman leader shall come to Syria, who shall burn down Solyma's [Jerusalem's] temple with fire, and therewith slay many men, and shall waste the great land of the Jews with its broad way (Sibylline Oracles 4.125-7).
It seems to me that if this were being written post AD 70, then the prophecy would have been altered to distinguish the fates of the city and temple. Christians did come to see the burning of the Temple as God's judgment on the Jewish leadership, but the events do not correspond closely enough to require Christ's parable to be a reference to it or the wording to be an after the fact description. A final note on Matthew and the city can be found in Matthew 27:8 ("For this reason that field has been called the Field of Blood to this day."). Matthew seems to view the city as still intact when he writes that.
Likewise, the cryptic statement in Matt 24, "let the reader understand" need not mean the "this prophecy has been fulfilled." Whenever Matthew wants to say that a prophecy has been fulfilled, he says so (for example, Matt 1:22; 2:15; 2:23; 3:15; 4:14; etc).
I understand Matthew 24 to be referring to the parousia. Matthew states that the distress of those days will be followed immediately by the coming of the Son of Man (24:29). This did not happen in AD 70. If Matthew is trying to portray Jesus as an unmatched prophet, he failed by including material that did not happen.
While Matthew contains a high Christology, this by no means means it has to be written after Mark who does not present such a high theology. (Easily explained if Mark's Gospel is meant for an audience who is new in the faith.) Paul's letters contain a high Christology, and most scholars date Paul (died ~64) before Mark (who they place ~70). Moreover, Paul's letters show that Christian traditions even earlier than his had a high Christology.
The same can be said for Matthew's high liturgy. In fact, one of the verses that is brought out to show Matthew came late in the first century or beyond is Matthew 18:17 based on the word "church." However, this ignores that the Greek word used there, ecclesia, enjoyed wide usage in the Septuagint to translate qahal, "sacred assembly," and was used by diaspora Jews.
There are a significant number of places in Matthew where the parallel account in Mark makes more sense to have been edited down than for Matthew to expand. It is possible to read Mark with the hypothesis that it came from Matthew and run into no redactional problems that challenge said hypothesis. However, reading Matthew as a redaction of Mark does cause such problems.
There are places where Mark uses a certain word but Matthew does not, even though he used that word in other places (for example "pherein"). This makes more sense with Mark editing Matthew than of Matthew copying Mark.
There are places where Matthew has phrases he likes and uses them consistently. Mark has parallels of most of these accounts and is very free in his translations of the phrases. It makes more sense for Mark to be free styling from Matthew than it does for Matthew to be forcing the phrase into his wording whenever he sees it in Mark. One of these phrases is opias de genomenes, found first in Mt 8:16 and Mk 1:32. Markan priority has to conclude that Matthew copied the form exactly as Mark had it the first time, then always and consistently used the same grammar whenever he found a similar phrase in Mark and introducing it himself in Mt 20:8 which has no parallel in Mark.
There are places where Mark combines details from both Matthew and Luke. An example of these duplicate expressions can be seen in Mark 1:32 compared to Mt 8:16 and Luk 4:40.
Mk 1:32 When evening came, after the sun had set, they began bringing to Him all who were ill and those who were demon-possessed.
Mt 8:16 When evening came, they brought to Him many who were demon-possessed; and He cast out the spirits with a word, and healed all who were ill.
Lk 4:40 While the sun was setting, all those who had any who were sick with various diseases brought them to Him; and laying His hands on each one of them, He was healing them.
In these parallels, Mark combines the introductory phrases from both Matthew and Luke. In this case, Markan priority would require that Luke know of both Matthew and Mark and consciously choose to use the exact phrase that Matthew does not. However, if Matthew writes first and Luke second, there is no such problem.
Matthew leaves semitisms in place where Mark smoothens them. This includes wording and patterns that Mark breaks. Yes, Mark has eight semitic words, but Matthew has many more semitisms (so does Luke, a plethora of semitisms). Many of Mark's semitisms seem to be added for drama while Matthew's flow naturally.
Adding to the semitisms are 12 times where Matthew (and Luke) uses the participle of a verb while Mark uses the past tense. Using a participle for the second verb in a set (and he answered, saying) is well-known when coming from a semitic language (all over the Septuagint) but is not used in normal Greek. Mark also uses these participles but not as often. It would be more likely to edit them out than to edit them back in.
Many more examples exist where Matthew and Luke agree with one another in wording and Mark is different.
Matthew and Luke both record 8 healing miracles. Mark has 10. The two left out of both Matthew and Luke are the saliva miracles (Mark 7:32-35 and 8:24). Did they both decide to skip the same miracles independently or did Mark add them from another source?
More details can be found here and here.