If time travel is possible, it seems to inevitably lead to paradoxes. These include consistency paradoxes, such as the famous grandfather paradox, and bootstrap paradoxes, where something is created out of nothing. One proposed class of resolutions to these paradoxes allows for multiple histories (or timelines), such that any changes to the past occur in a new history, independent of the one where the time traveler originated. We introduce a simple mathematical model for a spacetime with a time machine, and suggest two possible multiple-histories models, making use of branching spacetimes and covering spaces respectively. We use these models to construct novel and concrete examples of multiple-histories resolutions to time travel paradoxes, and we explore questions such as whether one can ever come back to a previously visited history and whether a finite or infinite number of histories is required. Interestingly, we find that the histories may be finite and cyclic under certain assumptions, in a way which extends the Novikov self-consistency conjecture to multiple histories and exhibits hybrid behavior combining the two. Investigating these cyclic histories, we rigorously determine how many histories are needed to fully resolve time travel paradoxes for particular laws of physics. Finally, we discuss how observers may experimentally distinguish between multiple histories and the Hawking and Novikov conjectures.