Prawdopodobnie pierwszym Polakiem odwiedzającym tereny dzisiejszej Kambodży był polski jezuita Wojciech Męciński, który wyruszył w 1638 roku z Makau na misję do Indochin.
Kolejnym znanym przypadkom obecności Polaków w tym rejonie dało początek zajęcie Indochin przez Francję i utworzenie z Kambodży francuskiej kolonii w 1864 roku. W tamtym czasie wielu Polaków służyło w Legii Cudzoziemskiej, jak też w regularnej armii francuskiej, pozostawiając po sobie spisane w czasie służby wspomnienia. Znalazł się także Polak (Antoni Kłobukowski) we francuskiej administracji kolonialnej, który opublikował później kilka prac antropogeograficznych dotyczących tego rejonu.
Oficjalne stosunki dyplomatyczne Polska i Kambodża nawiązały 24 stycznia 1956 roku. 2 lata wcześniej polskie siły wojskowe weszły w skład Międzynarodowej Komisji Nadzoru w Kambodży. W sierpniu 1968 roku nastąpiło otwarcie ambasady PRL w Phnom Penh, a stosunki między obydwoma państwami rozwijały się powoli do czasu przejęcia władzy Kambodży przez generała Lon Nola w 1970 roku. Ocieplenie stosunków nastąpiło ponownie po obaleniu reżimu Pol Pota w 1979 roku. W latach 80. nastąpiła wymiana kilku ważniejszych wizyt, nie pociągających za sobą jednak zawierania ważnych umów dotyczących bilateralnej współpracy.
Po upadku komunizmu w Polsce i w Kambodży w 1989 roku Polska była zaangażowana w proces demokratyzacji Kambodży. 15-16 stycznia 1990 roku w Paryżu odbyła się konferencja z udziałem stałych członków Rady Bezpieczeństwa ONZ, podczas której zapowiedziano zorganizowanie w Kambodży wolnych wyborów pod nadzorem ONZ. Zorganizowaniem i nadzorowaniem tych wyborów miał się zająć Program Wolontariuszy Narodów Zjednoczonych. W 1992 roku 15 wolontariuszy polskich współorganizowało i nadzorowało pierwsze demokratyczne wybory w Kambodży. Od października 1991 roku do marca 1992 roku działała w Kambodży Misja Przygotowawcza Organizacji Narodów Zjednoczonych w Kambodży (UNAMIC), w której brało udział 2 Polaków.
Od marca 1992 roku do września 1993 roku w Kambodży działała Tymczasowa Administracja Organizacji Narodów Zjednoczonych w Kambodży (UNTAC). W porozumieniu z ONZ i w ramach działania Tymczasowej Administracji Organizacji Narodów Zjednoczonych w Kambodży, w grudniu 1991 roku polscy żołnierze zostali przydzieleni do udziału w misji kambodżańskiej zakończonej jesienią 1993. Łącznie personel polski uczestniczący w misji UNTAC liczył 1254 żołnierzy i cywilów.
W 2005 roku Kambodża otworzyła w Polsce ambasadę regionalną na Europę Środkowo-Wschodnią, która działała do 31 grudnia 2008. Zgodnie z decyzją ministra spraw zagranicznych RP Ambasada RP w Phnom Penh została zamknięta 30 września 2008 roku. Obecnie Królestwo Kambodży nie posiada placówki dyplomatyczno-konsularnej w Polsce, a Kambodża należy do właściwości terytorialnej ambasady RP w Bangkoku.
Do dzisiaj kontakty Polski z Kambodżą pozostają jednymi z najmniej rozwiniętych spośród państw regionu Azji Południowo-Wschodniej.
