Historians of science tell use that it was actually Lemaitre, in 1927, who came up with the first value.
Neither of these claims is correct. The first value was determined by Lundmark, in 1925 (MNRAS, 85, 865). He didn't know it at the time. It is found in Table I on line 20. Lundmark took the same data he used in his 1924 paper (MNRAS, 84, 747) and fit a number of different models for the velocity-distance relation. The solutions all involved solving for a vertex motion (a systemic motion of the solar system relative to the external galaxies) and a "K-term" that accounts for the remaining contribution to the velocities. This procedure paralleled the one that Hubble would use in 1929. Lundmark tried 20 different combinations of data cuts and K-term formulations. Line 20, the last one in the table, is the precise formulation used by Hubble - a K-term linear in distance, with no constant offset. The coefficient of this relation is the Hubble constant.
The only quirk is that Lundmark expressed his distances in units of the distance to M31, and in order to convert the coefficient to absolute units we need to know that distance. By reverse-engineering Table III of the 1924 paper, we find that his preferred value at that time was 200 kpc. The coefficient on line 20 was 6.96. We divide by 0.2 Mpc for the distance to M31, and thus arrive at a Hubble constant of 35 km/s/Mpc. For once we have a Hubble constant from the 1920's that was actually too small compared to the modern value. Also notable, his value was the only one around that time that did not depend on Hubble's data. (The distance calibration was based on the magnitudes of novae.)
Why has Lundmark's epochal accomplishment not been recognized before? Lundmark was always his own worst enemy. Alan Sandage called him a "pure Baconian empiricist". In this case his preferred solution from Table I was line 18, a K-term that was a quadratic function of distance with a large positive constant offset and a negative 2nd-order term, which meant that velocities would reach a maximum and then decline as the distance became larger. He wrote down line 20, but attached no significance to it. All we can do now is look back and take note. It was the first-ever calculation of the Hubble constant, but it had no impact on anyone who followed.
Lundmark's value of 35 is enormously different from Lemaitre's value of 625, even though they nominally used similar methods and nearly the same data! Why the difference? Here are the reasons that I can figure out so far.
In "Did Edwin Hubble Plagiarize?" (2011, arXiv:1107.0442), Shaviv recalculated the slope that Lundmark could have derived and found 71.2 km/s/Mpc, twice the value of Line 20. Shaviv used the data from Lundmark's 1924 paper verbatim and thus did not correct for the vertex motion (unlike Lundmark's Line 20 value), perhaps explaining the different values.
Hermann Weyl actually attempted to calculate the Hubble constant two years earlier (1923, Raum, Zeit, Materie), and, while he had a decent distance to M31, he assigned it a velocity that was largely invention. Thus, while his estimate of the Hubble radius was in the right ballpark, it was too dicey to give him credit ahead of Lundmark.
Lundmark came up with two other remarkable results in this paper, which also have had little impact on the field.