Următoarea misiune importantă la care a participat Methodiu a fost la poporul evreu al khazarilor (860) în regiuneaHerson și în alte părți din sudul Rusiei. Cei doi frați trebuiau să găsească relicvele papei Clement I, care fusese torturat și îngropat acolo, și să convertească la creștinism cât mai mulți oameni posibil.

Pentru a-i putea convinge pe localnici, Constantin-Ciril a adresat rugăciuni lui Dumnezeu și în doar câteva luni a învățat limba ebraică, a citit cărțile acesteia, apoi a învățat limba samariteană și i-a uimit pe toți vorbind și citind în limbile lor. Tot cu rugăciuni, el calmează marea și reușește să scoată la suprafață moaștele Sf. Clement din marea. În călătoriile sale prin pământul khazar, întâlnește maghiari și evrei, oprește un atac asupra unui oraș creștin și explică necredincioșilor sensul ortodoxiei. El și Metodiu au convertit aproximativ 200 de persoane și au lăsat amintirea „unui astfel de om care ne-a explicat prin cuvânt și exemplu că credința creștină este sfântă” (Sfântul Clement al Ohridei , „O viață cuprinzătoare a lui Constantin Chiril”).