The early sense of the word “accost” was nautical, so much so that it was often written accoast, as if the meaning were “to lie along the coast of.”
The original meaning was not far from that, because the word was derived from the Latin prefix ad, to, plus costa, which, though actually meaning “rib,” was extended to “side.” So the nautical meaning was “to lie alongside,” almost, as it were, rib to rib.
Later the meaning became less exact, “to approach for the purpose of addressing,” and now we use it most frequently just in the sense of “to address.”