Russell was not the first to discover "his" paradox. By June 1901 when he arrived at it (it was not published until the first edition of Principia in 1903), it was already known for a while to the Hilbert's circle at Göttingen. Russell did not belong to that circle, so his rediscovery was independent, but he was familiar with Schröder's Algebra of Logic (1890), the precursor to Principia, where Schröder argued that admitting "all objects of thought" into a class leads to contradictions. Here is Ortiz Hill:
In a November 7, 1903 letter, Hilbert told Frege that Russell's antinomy was already known to them in Göttingen. Hilbert added that he believed that Ernst Zermelo had found it three or four years earlier after having learned of other, even more convincing, contradictions from Hilbert himself as many as four or five years before. Hilbert further commented that the idea that "a concept is already there if one can state of any object whether or not it falls under it" did not seem adequate to him. What would be decisive, he states, "is the recognition that the axioms that define the concept are free from contradiction.
Concrete evidence corroborating Zermelo's finding of the paradox is to be found in a note that he sent to Husserl in April 1902, in which Zermelo conveyed his proof... In Zermelo's opinion... Schröder had been basically right, but his reasoning had been faulty. According to Zermelo's argument as recorded by Husserl: given a set M which contains each of its sub-sets m, m'… as elements, and a set M0 which is the set of all sub-sets of M, which do not contain themselves as elements, it can then be shown that M0 both does and does not contain itself."
The principle Hilbert rejected (roughly, that every non-vague property defines a set of objects having it), now known as the axiom of (unrestricted) comprehension, was broadly used by 19th century logicians and mathematicians. It appears explicitly as the "third generation principle" of ordinals in Cantor's mathematico-philosophical opus Foundations of the General Theory of Sets (1883), and as the Basic Law V in Frege's Foundations of Arithmetic (1884), another of Russell's points of departure. The unraveling that apparently led both Russell and Zermelo to the paradox started with the Schröder's monograph, and the Cantor's diagonal argument published in 1891. Russell commented that it was studying Cantor's theories that led him to the antinomy that ended the "logical honeymoon" of the early work on Principia. In the diagonal argument a list of "all" sequences is first "compiled", and then the list itself is manipulated to produce a sequence that does not belong to it, while it is supposed to.
By 1895 Cantor already realized that his argument implies another paradox, now called after Burali-Forti who published it in 1897, that of the ordinal of all ordinals both having and not having a successor (or more precisely, its version for the alefs). As a result, according to Zermelo's remarks in Cantor's Collected Works, in a far cry from the broad sweep of 1883 Cantor excluded non-countable ordinals from his work:
"The reason for this omission was apparently, first, the still absent proof that every cardinality is an alef, and second - that Cantor already had some skeptical doubts concerning "all" ordinal or cardinal numbers based on the already known to him "antinomy of Burali-Forti"..."
The difference between the "Burali-Forti" paradox and the "Russell"'s, is that the latter does not require complicated notions like ordinals or cardinality. But they both rely on the unrestricted comprehension for definition, and arrive at the contradiction through the same kind of self-referential exploit. Russell's paradox of the barber (who shaves those and only those who do not shave themselves) stands in the same relation to "his" paradox, as the diagonal argument does to "Burali-Forti"'s. In the former there are presuppositions that can be rejected (existence of the barber, countability of the continuum), thus disarming the paradox, but in the latter the way out is blocked by the axiom of comprehension.
One could say that the paradoxes of self-reference were "in the air", and the particular type of reasoning Zermelo and Russell distilled was "in the air" too. But, as Ortiz Hill notes, Russell was "the first to publicize Frege's errors and to bring the point home to Frege himself", indeed he devised the paradox of the barber to popularize the issue in non-technical terms.