The question when the Influenza virus first infected humans is perhaps an academic one. We normally are only interested in the present (which strain of the virus is circulating at the moment and how can we protect ourselves from it) or in the future (which novel subtype of the virus is emerging that could endanger us).
The Spanish philosopher, essayist, poet and novelist George Santayana (1863-1952) once said that "Those who cannot remember the past are condemned to repeat it". And he was right because the history of the Influenza can possibly teach us how it will evolve to create another pandemic.
. Influenza A and B viruses have a similar structure, whereas influenza C is more divergent, which suggests it diverged earlier from the original virus.
Hemagglutinin (HA) is the major envelope glycoprotein of both Influenza A and B viruses, while hemagglutinin-esterase (HE) in Influenza C viruses is a protein homologous to HA. Influenza A virus HA genes are classified into 18 subtypes (H1-H18), according to their antigenic properties, whereas Influenza B (HA) and C virus (HE) are not (yet) classified into subtypes. We know that these proteins change ever so slightly over time in order to evade the immune system. If you can guess how much time it takes between each change, you can also estimate when it first started to change.
Scientists were able to ascertain that the earliest divergence time between subtypes of Influenza A virus HA-genes was estimated to be about 2,000 years ago. Also, the divergence time between A and B viruses was estimated to be about 4,000 years ago, whereas Influenza A and B virus HA-genes and Influenza C virus HE-genes diverged about 8,000 years ago.
But the question remains: when did the first proto-Influenza virus infect humans?
 Webster et al: Evolution and ecology of influenza A viruses in Microbiological Reviews - 1992
 Suzuki, Nei: Origin and Evolution of Inﬂuenza Virus Hemagglutinin Genes in Chinese Journal of Experimental and Clinical Virology - 2002