Fins a 1774, la regió va pertànyer al Khanat de Crimea. Kherson va ser fundada el 1778 per Grigorii Aleksàndrovitx Potiomkin, a les ordres de Caterina la Gran. La ciutat va ser construïda sota la supervisió del general Ivan Gannibal, en el lloc on hi havia una petita fortalesa anomenada Aleksandersxanz. El mot Kherson és una contracció de Quersonès, una colònia grega antiga fundada fa aproximadament 2500 anys en la part sud-oest de Crimea. Un dels primers edificis al Fort de Kherson va ser l'Església de Santa Caterina on Potiomkin va ser finalment enterrat. L'últim tarpan va ser capturat prop de Kherson en 1866.
L'Església de Santa Caterina, que va ser construïda pels volts de 1780, seguint suposadament els dissenys d'Ivan Starov, i conté la tomba del Potiomkin.
Salomon Rosenblum, més tard conegut com a lloctinent Sidney Reilly, un agent secret, aventurer internacional i playboy que durant un temps va estar contractat pel servei secret britànic. Se suposa que va ser la inspiració real per al caràcter de l'espia de ficció James Bond
Kherson
Rzeszów, Polònia
Zalaegerszeg, Hongria
Xumen, Bulgària
Kent, Washington, Estats Units
Zonguldak, Turquia
Oslo, Noruega
