As I already mentioned, A. Lubotzky pointed out, in his recent Colloquium Lectures, that expander graphs (which were usually said to go back to a paper of Pinsker in 1973) already appeared in a paper of Barzdin and Kolmogorov from 1967. This was naturally in Russian, but the paper is reproduced in English translation in the selected works of Kolmogorov.
The paper is very interesting. It contains, indeed, a definition of what are recognizably expanders; it contains, before Pinsker, and with a similar probabilistic argument, a proof that “most” graphs, in a certain sense, are expanders; and it contains, most interestingly for me, an application of expanders which is of great interest, and which I didn’t know before. (I’d be interested to know if other readers had already heard of it).
In a second post, I will try to explain what Barzdin and Kolmogorov did in some detail, as far as my understanding goes. For the moment, before a few general remarks, here is the problem that they solve. The question is roughly: “how much volume does one need to embed a graph in?” More precisely, they consider a finite oriented graph 
Amusingly, 1967 is also the year when D. Kazhdan published his paper introducing Property (T). As is well-known, and explained for instance in the recent book of Bekka, de la Harpe and Valette, the first explicit construction of expanders, due to Margulis, relied on Property (T); in hindsight, it is rephrased as saying that any infinite discrete group 
Now here comes an idle discussion of priority and the like, which platonists might want to avoid. The paper of Barzdin and Kolmogorov contains a footnote saying that the details and sharpest results are due to Barzdin; the selected works of Kolmogorov contains a comment by Barzdin that says that the basic ideas are entirely due to Kolmogorov. So it’s not completely clear (to a random reader like me) which of the two authors precisely did come up first with the idea of expanders. One is tempted to suspect that it was Kolmogorov; if that is the case, he must have been past 60 when the idea came up — the paper appeared when he was 64 –, and that would be a very striking counterexample to the common perception that mathematics is a young person’s game… (Rigorous chronologists might like to point out that Selberg’s “3/16” theorem predates the Kolmogorov-Barzdin paper as well as Kazhdan’s Property (T) paper, so that an explicit construction of expanders was, in some sense, known before they were defined; unless, that is, it is discovered that Gauss, Euler or Kepler, in a particularly abstruse private letter or notebook, had anticipated the discovery…)
[Query: the proof of existence of expanders in the paper of Barzdin and Kolmogorov goes by computations with binomial coefficients and the like; now, I don’t want to be more of a probabilist than Kolmogorov, but does anyone know if someone has written somewhere a “clean” proof, using instead the basic properties of binomial random variables and standard analytic/probabilistic inequalities? I would be surprised if this wasn’t possible, and I’ll certainly look for something like that before teaching — probably next semester — about expanders.]
Final remark: for a fairly wide-ranging discussion of the mathematical contributions of Kolmogorov, there is a nice book, available either in French or in English translation (I was one of the translators, which was very interesting since I had no idea previously that Kolmogorov had been influential in mathematical logic or in algebraic topology…) The Barzdin-Kolmogorov paper is mentioned in the bibliography of one chapter, but is not discussed in detail.
Given that the paper was coauthored, there isn’t a priority issue at all; priority is due to both of them.
As for the age of 64 – surely we can come with examples of a new idea introduced by somebody older? (Even in the romantic 19th century, weren’t some players – i.e. Weierstrass, Sylvester – active until quite old?)
Maybe “priority” was not the right word; what I mean is, was it Kolmogorov or Barzdin who came up first with the idea of expanders? Of course, the answer might still be “both”, if the spark arose, say, during a conversation in front of a blackboard. I don’t think the question is in bad taste (not that you suggested it), in view of the duelling footnote and comment in the collected works…
As for finding another example with someone even older, of course that wouldn’t be too surprising. But such an important idea? That sounds harder…
Here’s a contender: Grothendieck wrote the about 2000-pages long book Les Dérivateurs in 1990-1991 aged 63, see http://www.math.jussieu.fr/~maltsin/groth/Derivateurs.html (And he probably has had some other profound ideas still later on…)
I have no problem with the suggestion that the expander concept had already appeared in some implicit form in Barzdin and Kolmogorov’s work, even possibly earlier before Pinsker’s work, but this suggestion must not be stretched too far to overshadow what Pinsker accomplished in his seminal 1973 paper. His work is far deeper than formally introducing and defining an expander. He provided a remarkable proof of existence of a concentrator with at most 29n edges, first of any such linear size concentrators. Most people who cite his work don’t even take the time to go through his paper to appreciate the complexity and elegance of his proof. As important as it is, the proof of existence of an expander was not even included in the main body of the paper, but only placed in the appendix…