We have developed a simple model for the evolution of interstellar dust, which relates elemental depletions to the physical processes involved, including stardust injection, accretion in clouds, and dust destruction in interstellar shocks. We compare the results of this model to observed cloud and intercloud depletions of Si, Mg, and Fe and derive dust destruction and accretion rates. The results show that the much lower depletion in the intercloud phase as compared to the cloud phase implies that the dust destruction timescale for Si-bearing dust is comparable to the mixing timescale from the cloud to the intercloud phase and thus much shorter than the stardust injection timescale. The derived average lifetime for Si-bearing dust (6 x 10(7) yr) is considerably less than theoretical calculations for silicates (3 x 10(8) yr) predict. Thus, in agreement with other studies, we conclude that a major fraction of the elemental silicon is locked up in a relatively volatile (binding energy, E(b) similar or equal to 2 eV) dust component. In contrast, the lifetime for Fe-bearing dust (5 x 10(8) yr) is consistent with a refractory (E(b) similar or equal to 5 eV) reservoir. Derived accretion rates for these elements are consistent with expected collision rates in diffuse clouds and imply little chemically driven differentiation upon accretion. The implications of these lifetimes for our understanding of the origin and evolution of interstellar dust are briefly examined.