According to the list of Purāṇas provided in A Concise Encyclopaedia Of Hinduism - Volume 2 by Swami Harshananda, Vāyu Purāṇa from A.D. 200 appears to be the oldest.
| S. No. | Name of the | Number of | Period of |
| | Purāṇa | Ślokas | Composition |
| | | | |
| 1. | Agni | 16,000 | A.D. 800 |
| 2. | Bhāgavata | 18,000 | A.D. 600 |
| 3. | Bhaviṣya | 14,500 | A.D. 500-900 |
| 4. | Brahma | 10,000 | A.D. 1300 |
| 5. | Brahmāṇḍa | 12,000 | A.D. 400 |
| 6. | Brahmavaivarta | 18,000 | A.D. 1000 |
| 7. | Garuḍa | 18,000 | A.D. 900 |
| 8. | Kūrma | 18,000 | A.D. 500 |
| 9. | Liṅga | 11,000 | A.D. 600-1000 |
| 10. | Mārkaṇḍeya | 9,000 | A.D. 300 |
| 11. | Matsya | 14,000 | A.D. 300 |
| 12. | Nāradīya | 25,000 | A.D. 900-1600 |
| 13. | Padma | 55,000 | A.D. 800 |
| 14. | Skanda | 81,000 | A.D. 700-900 |
| 15. | Vāmana | 10,000 | A.D. 900 |
| 16. | Varāha | 24,000 | A.D. 800-1100 |
| 17. | Vāyu | 24,000 | A.D. 200 |
| 18. | Viṣṇu | 23,000 | A.D. 300 |
The author however notes "the period of compilation is very approximate."
P. L. Bhargava in his paper The Origin and Development of Purāṇas and Their Relation With Vedic Literature lists Vāyu, Brahmāṇḍa, Matsya, Viṣṇu and Mārkaṇḍeya Purāṇas among the oldest but doesn't say which of them is the oldest.
The internal evidence of the Purāṇas makes it absolutely clear that
they were written at widely different times. As a rule, the later the Purāṇa,
the more its historical matter is burdened with explanatory myths and the
latest Purāṇas are altogether relieved of historical matter. Reversely, the
older the Purāṇa, the less its genealogies are burdened with myths and the
more they approximate to the Vedic evidence. Judged from this, the oldest
Purāṇas, so far as genealogies and accounts of persons mentioned in the
genealogies are concerned, are the Brahma, the Vāyu, the Brahmāṇḍa and
the Matsya, all of which purport to be narrated by the sūta Lomaharṣaṇa.
Later than these four but older than the others is the Viṣṇu Purāṇa. Seven
other Purāṇas, the Bhāgavata, the Garuda, the Agni, the Padma, the
Liṅga, the Kūrma and the Mārkaṇḍeya contain historical matter in varying
degree. Among the remaining Purāṇas, the Bhaviṣya professedly does not
deal with the ancient past and the other five viz. the Nārada, the Brahmavaivarta, the Varāha, the Vāmana and the Skanda are purely sectarian
works free from all historical matter.
The chronology of the Purāṇas, however, is not as easy as this. For
instance the Brahma, whose genealogical account is ancient, contains other
material which is comparatively quite late. On the other hand the
Mārkaṇḍeya whose genealogical material is not of much value yet appears
to be quite ancient if we judge it from the other material that it contains.
It is the least sectarian of the Purāṇas which tended to become more and
more sectarian with the passage of time. If we cast a glance over the entire
contents of the Purāṇas, the oldest Purāṇas appear to be the Vāyu, the
Brahmāṇḍa, the Matsya, the Viṣṇu and the Mārkaṇḍeya all of which
must have been composed by the 4th century A. D. although the Matsya
and the Mārkaṇḍeya contain some material which appears to be much
later. The first four of these Purāṇas contain the lists of kings who ruled
in the Kali age and this list ends with the foundation of the Gupta dynasty
in the beginning of the 4th century A. D.
There is another way of judging the relative chronology of some of
the Purāṇas. The Viṣṇu contains the oldest version of the Kṛṣṇa story.
The versions of the Brahma and the Bhāgavata are later and those of the
Padma and the Brahmavaivarta which mention the name of Rādhā are later
still. This proves that the Brahma to a large extent and the Bhāgavata
wholly are later than the Viṣṇu, while the Padma and the Brahmavaivarta
came later still. Since Alberuni mentions all the Purāṇas they must all have
been composed by 1000 A. D.