Kjelstraumen er nemnd i kong Sverre si tid. Birkebeinarane sine menn innhenta to av baglarane sine skip på veg til Bergen i 1260. Dei kom i kamp i Kjelstraumen. Det eine skipet rende opp på eit skjer og vart eit lett bytte for jarlen. Det andre skipet kom seg unna til Bergen og melde frå om at fienden var nær. Tradisjonen fortel elles at det var falkestasjon i Kjelstraumen i mellomalderen. Jaktfalken hadde stort verde; han vart gjeven som gåve til kongar og jarlar.
Dei første herberga som er nemde i Nordhordland, er Salhus nord for Bergen og Kvalvågen i Austrheim, kring 1500. Men i 1610 vart gjestgjevarstaden lagd til Kjelstraumen, som var prestegods. Lindåspresten Hans Nilssøn Hess søkte i 1610 til kongen, Christian IV , om stadfesting, etter at lensherren på Bergenhus, Lauritz Kruse, hadde gjeve løyve til å setja opp eit hus i Kjelstraumen, til gagn og beste for vegfarande.
Peder Claussøn Friis fortel i Norrigis Bescrifuelse at det låg eit blindskjer i Kjelstraumen. I 1632 gjekk sju nordlandsjekter på dette skjeret og sokk. I 1877 vart det sprengt vekk.
Økonomisk må gjestgjevarstaden ha stått seg godt. Då den første fattiglova vart sett ut i livet for gamle Lindås prestegjeld i 1756, var det berre ein mann i Lindås som vart rekna mellom dei fornemme: gjestgjevaren i Kjelstraumen, Ole Lagesen. Han laut ut med 10 Rdl. til fattigkommisjonen. I 1799 kjøpte Christopher Kahrs gjestgjevarstaden. Sonen Christ Kahrs løyste borgarbrev som handelsmann i 1812, og det var fast tingstad i mange år, vår og haust. Her vart det dampskipsstoppestad, og det første postopneriet i Austrheim vart lagt hit i 1870.