It is not a story, Newcomb published his observation in a two page Note on the Frequency of Use of the Different Digits in Natural Numbers (American Journal of Mathematics Vol. 4, No. 1 (1881), pp. 39-40), which you can read under the link. Here is the opening paragraph:
"That the ten digits do not occur with equal frequency must be evident to any one making much use of logarithmic tables, and noticing how much faster the first pages wear out than the last ones. The first significant figure is oftener I than any other digit, and the frequency diminishes up to 9. The question naturally arises whether the reverse would be true of logarithms. That is, in a
table of anti-logarithms, would the last part be more used than the first, or would every part be used equally? Tne law of frequency in the one case may be deduced from. that in the other. The question we have to consider is, what is the probability that if a natural number be taken at random its first significant digit will be $n$, its second $n'$, etc."
He proceeds to select two numbers "at random", and looks for the probability of the first significant digit of their ratio to be $n$. It turns out that the fractional parts of the ratio's logarithms are equally probable, so $n$ is $1$ in about $30\%$ of cases, and any other one digit in less than $20\%$ of cases.
Benford in The Law of Anomalous Numbers (Proceedings of the American Philosophical Society, Vol. 78, No. 4 (Mar. 31, 1938), pp. 551-572) starts with the same observation about logarithmic tables, but proceeds to test the law on 20 different datasets, and gives an explicit formula for the frequency as $\log(\frac{n+1}n)$, as well as its refinements. He does not seem to be aware of Newcomb's note.