Damage evolution and time-to-failure are investigated for a model material in which damage formation is a stochastic event. Specifically, the probability of failure at any site at time t is proportional to sigma(i)(t)(eta), where sigma(i)(t) is the local stress at site i at time t and differs from the applied stress because of the stress redistribution from prior damage. An analytic model of the damage process predicts two regimes of failure: percolationlike failure for eta less than or equal to 2 and ''avalanche'' failure for eta > 2. In the percolationlike regime, failure occurs by gradual global accumulation of damage culminating in a connected cluster which spans the system. In the avalanche regime, failure occurs by rapid growth of a single crack after a transient period during which the critical crack developed. The scalings of the transient period, the subsequent crack dynamics, and the time-dependent probability distribution for failure are determined analytically as functions of the system size and the exponent eta. Specific predictions are that failure is more abrupt with increasing eta, failure times scale inversely with a power of the logarithm of system size, and the distribution of failure times is a double exponential and broadens with increasing eta, so that the failure becomes less predictable as it is becoming more abrupt. The conditions for the transition to the rapid growth regime are identified, offering the possibility of early detection of impending failure. In a companion paper, numerical simulations of this failure process in two-dimensional lattices are compared in detail to the analytical predictions.