Terdapat bukti yang jarang akan terdapatnya pendudukan manusia di wilayah Kemboja pada zaman Pleistosen, termasuklah alat-alat kerakal kuarza dan kuarzit yang terdapat di deret-deret rumah sepanjang Sungai Mekong di wilayah-wilayah Stung Treng, Kratié dan Kampot, tetapi pentarikhannya sukar boleh diharap.[2]

Terdapat sedikit bukti kaji purba yang menandakan bahawa masyarakat pemburu-pengumpul menduduki Kemboja pada zaman Holosen: tapak kaji purba yang paling tua di Kemboja kononnya adalah gua Laang Spean di Wilayah Battambang yang tergolong dalam zaman Hoabinh. Usaha penggalian di lapisan-lapisan paling dasarnya membuahkan serangkai pentarikhan radiokarbon yang menjangkau seawal 6000 SM.[2][3] Manakala lapisan-lapisan atas di tapak gua tersebut membuahkan bukti peralihan ke zaman Neolitik yang mengandugni tembikar seramik yang tertua di Kemboja.[4]

Rekod-rekod kaji purba bagi tempoh dari Holosen ke Zaman Besi masih jarang. Lain-lain tapak prasejarah yang belum tentu tarikhnya adalah Samrong Sen (yang tidak jauh dari ibu kota lama Udong), di mana penyelidikan pertama bermula pada 1875,[5] dan Phum Snay di wilayah utara Banteay Meanchey.[6] Usaha penggalian di Phum Snay menemukan 21 buah kubur dengan persenjataan besi dan kecederaan di tempurung tengkorak yang menungkin menandakan peperangan di zaman lampau, mungkin sekali dengan negeri-negeri terbesar di Angkor.[7] Artifak prasejarah sering ditemui dalam kerja pelombongan di Ratanakiri.[2]

Akan tetapi bukti prasejarah yang paling menghairankan di Kemboja adalah seaneka "tembokan tanah bulat" yang ditemui di tanih merah berdekatan Memot dan kawasan Vietnam bersebelahan pada lewat 1950-an. Fungsi dan umurnya masih dipertikai tetapi antaranya datang dari seawal alaf ke-2 SM.[8][9]

Suatu peristiwa penting dalam prasejarah Kemboja adalah kedatangan petani padi terawal dari utara ke Kemboja secara beransur-ansur mulai lewat alaf ke-3 SM.[10]

Besi dikerjakan seawal sekitar 500 SM dengan buktinya yang datang dari Penara Khorat yang kini dalam wilayah Thailand. Di Kemboja terjumpanya petempatan Zaman Besi di bawah Baksei Chamkrong dan lain-lain kuil Angkor sementara tembokan tanah bulat terdapat di bawah Lovea iaitu beberapa kilometer di barat laut Angkor. Tempat pengkebumian yang jauh lebih berbuah daripada lain-lain jenis bahan penemuan, membuktikan peningkatan keterdapatan makanan dan perdagangan (walaupun dalam jarak jauh: pada abad ke-4 SM sudah terjalinnya hubungan perdagangan dengan) serta kewujudan tatatingkat sosial dan susunan tenaga kerja. Tanah perkuburan Phum Snay dihiasi dengan persenjataan dan rangka yang menunjukkan bukti kecederaan akibat keganasan yang menandakan pertelingkahan antara pelbagai suku di kawasan berkenaan ekoran lokasinya yang sesuai untuk perdagangan.[10][11]

Manik-manik kaca juga adalah antara artifak Zaman Besi yang penting sekali. Pelbagai jenis manik kaca ditemui daripada beberapa tapak di seluruh Kemboja, misalnya tapak Phum Snay di barat laut dan tapak Prohear di tenggara, menandakan bahawa terdapat dua jaringan perdagangan pada zaman itu. Kedua-dua jaringan tersebut terpisah oleh zaman dan ruang, menandakan bahawa terdapat peralihan dari satu jaringan ke jaringan yang satu lagi sekitar abad ke-2 ke abad ke-4 M, barangkali sejajar dengan perubahan dalam kekuasaan sosiopolitik.[12]