In a book that I read (forgot the title) they found HIV in a frozen blood sample from a Norwegian sailor who died in 1960. Apparently he caught it from a prostitute in an African port. The doctors saved the blood sample because he died so quickly from an unknown disease.
I remember reading a newspaper article about a black teenager in St. Louis who was dying from a mysterious illness (in the 1960s, I think). The doctors saved a sample of his blood and/or tissue, and it was eventually determined that the teenager had had AIDS.