Köthel war ursprünglich eines slawische Siedlung. In den alten Urkunden des Mittelalters schrieb man das Dorf noch "Cotle", das soviel wie "Kessel" bedeutet. Wann genau das Dorf gegründet wurde, ist nicht überliefert. Die erste urkundliche Erwähnung erfolgte jedoch schon im Jahr 1238.
Die Geschichte Köthels ist eng mit der des Nonnenklosters Reinbek verbunden. Das Kloster, das seinen Ursprung in Hoibeke auf Oher Gemarkung hatte, wurde nämlich im ersten Drittel des 13. Jahrhunderts nach Köthel verlegt. So wurde aus "Cotle" für kurze Zeit Reinbek, denn das Dorf nahm den Namen des Kloster an. Als die Nonnen ihren Sitz in Köthel später aufgaben und das Kloster an seinen endgültigen Standort, dem heutigen Reinbek, verlegten, nahmen sie den Namen mit. Von da an hieß Köthel wieder Köthel. Noch heute erinnert der Straßenname "Klosterberg" daran, daß es hier einmal ein Kloster gab.

Die Zeit der Klosterherrschaft war eine der wenigen Perioden in der Geschichte des Dorfes, in der sowohl der lauenburgische als auch der stormarner Teil des Dorfes unter einer Herrschaft vereint waren. Sowohl der holsteinische Graf Adolf IV. als auch der Herzog Albrecht von Sachsen-Lauenburg schenkten dem Konvent ihre durch die Bille getrennten Teile Köthels. Bis heute hat sich ja die Teilung in Köthel/ Lauenburg und Köthel/ Stormarn gehalten.

Als das Reinbeker Kloster im Zuge der Reformation aufgelöst wurde, hatte diese kurze Periode des vereinten Köthels ein Ende. Herzog Magnus von Lauenburg zog seinen Teil Köthels wieder ein, während das heutige Köthel/ Stormarn dem neuen Amt Reinbek angegliedert wurde. Im Jahre 1609 kam das stormarnsche Köthel dann zum Amt Trittau.
Köthel lag von jeher an einer wichtigen Fernhandelsverbindung, der sogenannte Möllner Landstraße. Der Weg führte von Trittau kommend über Köthel weiter nach Mölln und in das Mecklenburgische hinein. So ist es nicht verwunderlich, daß König Friedrich V. von der Pfalz, König von Böhmen, im Jahre 1621 durch Köthel kam und hier in einem Gasthaus übernachtete.