The term "allophone" refers to two different things. One is an actual physical realization in a given context. For example, in English the lips start to continuously protrude on consonants in anticipation of a following round vowel in the syllable, for example in "scoot" as opposed to "skate". Or, the velum starts to lower about half-way into a vowel before a nasal, and goes from open to closed about a third of the way into the vowel after a nasal. The exact degree and time course of such effects is language-specific and part of what you learn when you learn the pronunciation of a language. We can call these "physical allophones": the crucial thing about them is that they don't involve crisp categories, they involve continuous functions. The second use of "allophone" pertains to actual categorial changes, but changes of a special type, namely where there is no "contrast" involving the choice of sounds (aspiration in English would be a classic example).
All cases of "sound change" start as some continuous-detail change in pronunciation, and at some point the changes become sufficiently large that they are re-analyzed as changes in discrete symbolic sound, rather than "amount" parameters in the physical realization of sounds. Unfortunately, nowhere near enough is known about the perceptual mechanisms for getting from continuous physical sound to a symbolic representation as discrete segments, and the production mechanisms for getting from the intent to produce a segmental output like [pʰlʊwm] "plume", to the actual production. This is the "and then a miracle happens" part waiting to be filled in.
Allophones in the second sense (i.e. as specific different segments derived from a single underlying source, according to some rule of distribution), especially the contextually-derived member(s) such as the flap or aspirated stops in English, have the property that they come exclusively from a given segment, so there is complete inter-translatability between output allophones and underlying phonemes – the allophone [pʰ] always derives from /p/ in foot-initial position, and /p/ in foot-initial position always becomes [pʰ]. Learning such relations is trivial, However, it is easy to obscure such relations, for example, all you have to do is add some rule that re-arranges syllable or foot structure, and you could end up with aspirated stops that are not foot-initial in the final output (hypothetical [ə.pʰə.ˈlaɪ] from ə.pʰˈlaɪ "apply"), or unaspirated stops (from original syllable-final stops) that become syllable- and foot-initial. In that case, inter-translatability between phoneme and allophone exists at a derived stage, but not at the surface. And by definition, "allophone" is a relationship that holds between underlying and surface forms. Notice that aspiration in American English is not completely surface-regular, since you have different aspiration facts in "militaristic" versus "capitalistic", even though the stress and syllabification patterns of the words are the same. The reason for the difference is that the source words, "military" vs. "capital", have different stress patterns, and aspiration reflects the source stress, not the surface stress.
In the case of voiced / voiceless fricatives in English, there are quite a number of factors involved. One is the loss of short final vowels, which leads to voicing of original s in the verb "house" ([haʊz]) but not the noun [haʊs]. Deletion of vowels made it impossible to predict on the surface whether a fricative would be voiced or voiceless – the voicing rule became "opaque" (see Kiparsky 1968 "Historical Linguistics", Dingwall ed., and zillions of subsequent publications). The second major cause of the allophone-to-phoneme shift is loan words, either from French or from other dialects of English (not all dialects of English had exactly the same allophonic rule). In French, /s,z; f,v/ are completely autonomous phonemes, and via the introduction of many loanwords from French, the idea that [v,z] were predictable variants of /s, f/ became untenable.