The largest contribution to the CP violating K_L-K_S mixing parameter epsilon_K comes from second order weak interactions at short distances and can be accurately determined by a combination of electroweak perturbation theory and the calculation of the parameter B_K from lattice QCD. However, there is an additional long distance contribution to epsilon_K which is estimated to be of order 5%. Here recently introduced lattice techniques for computing the long-distance component of the K_L-K_S mass difference are generalized to this long-distance contribution to epsilon_K.