Several types of defect structures in PbWO4 and CaMoO4 are studied within the framework of density functional theory. The electronic structure of isolated oxygen vacancies, oxygen and Pb or Ca double vacancies, and substitutional Y are modeled using a supercell approximation. We find that the main effect of oxygen vacancies in PbWO4 and CaMoO4 is the introduction of states of W or Mo d character into the band gap. The energies of these defect states are very sensitive to their charge. The absence of negative charge in the vicinity of an oxygen vacancy tends to destabilize the electronic structure and may cause lattice distortion. In addition, we also present preliminary results of simulations of interstitial oxygen atoms in CaMoO4, finding a relatively stable configuration with the interstitial O forming a weak bond between two MoO4 clusters. While PbWO4 is currently of greater technological interest, we were able to carry out more extensive calculations for CaMoO4, including lattice relaxation, large simulation cells, and more complicated defects. The structural and chemical similarity of the two materials suggests that their defect properties may also be similar.