Zahavi's original formulation of the handicap principle is somewhat vague with respect to precisely why costly signals are inherently believable. My reading is that Zahavi viewed handicaps as believable because they cause natural selection to "screen" signallers more intensely. For example, weak individuals are always more likely to be caught by predators than strong individuals. Adding ornaments or handicaps can exagerate the difference in predation rates, assuming that a handicaps hinders weak individuals more than it would hinder a strong one. Thus in the pool of surviving individuals with no ornament there may be a bias toward strong individuals, but in the pool of surviving indivduals who do bear ornaments this bias will be even larger. As a result, carrying a handicap - and surviving nonetheless - serves as a statistical signal of strength.
The modern interpretation of Zahavi's handicap principle differs somewhat. In this interpretation, receivers favor large ornaments or handicaps. Each signaller makes a strategic choice of how large of a handicap to produce, taking into account both the cost of doing so, and the benefit that will come from the response of the signal receiver. This choice need not be a conscious decision or calculation on the part of the signaller; it can be a decision rule that is encoded by the genes and tuned through the action of natural selection. Relative to weak individuals, strong individuals can assume greater handicaps at lower costs, and so they will choose to produce larger ornaments. As a result, handicap size serves as a reliable signal of strength - and thus the receivers' preference for large handicaps is justified.
Alan Grafen (1990) distinguishes clearly between these two interpretations of the handicap, calling the former a "survival handicap" and the latter a "strtategic choice handicap." Early population-genetic models of the handicap principle by focused on the survival handicap interpretation. These papers, by John Maynard Smith (1976,1978), Davis and O'Donald (1976), Ilan Eshel (1978), and Graham Bell (1978), found limited support for this version of Zahavi's hypothesis. Subsequent game-theoretic work focused on the strategic choice interpretation. An underappreciated paper by Nur and Hasson (1984) lays out the basic idea, Alan Grafen's (1990) paper provided the first full game-theoretical formalization and John Maynard Smith (1991) simplified Grafen's argument with his usual incisive clarity.