Der Ort wurde wahrscheinlich zwischen dem 1. und 6. Jahrhundert als Fischerdorf von einem Khmer-Volk gegründet. Zu dieser Zeit lebten in der Region noch keine Vietnamesen. Die Herrschaft über das Gebiet besaß nominell das weiter im Westen liegende Reich Funan. Später wurde Funan von dem Volk der Kambuja eingenommen, die zum Reich Chenla gehörten, das seinerseits später in Angkor aufging. Diese machtpolitischen Verschiebungen hatten aber nur wenig Einfluss auf das kleine Fischerdorf.
Das Land war von derart unzugänglichen Wäldern und Sümpfen umgeben, dass die dort lebenden Khmer-Fischer ihre Siedlung Prei Nokor (Dorf im Wald) nannten. Doch aufgrund ihrer Lage auf festem Boden unmittelbar nördlich des sumpfigen Deltas und auf drei Seiten von schiffbaren Wasserwegen umgeben, begann der Aufstieg des Ortes.
Als Chenla vom Khmer-Reich Angkor vereinnahmt wurde, das bis zum 15. Jahrhundert die Herrschaft über die Region hatte, erlebte Prei Nokor eine erste Blüte als Umschlaghafen für kambodschanische Schiffe, die den großen Mekong-Fluss befuhren. Bis zum 17. Jahrhundert entstand dort eine Garnison und eine Handelsgemeinde, zu der auch malaiische, chinesische und indische Händler gehörten.