We hypothesized that instruction in the criteria of scientific arguments, in combination with constructivist epistemic beliefs, would produce greater learning about physics concepts. The study was a randomized experiment, where college undergraduates (n = 88) discussed, in pairs over the Web, several physics problems related to gravity and air resistance. Prior to their discussions, one-half of the dyads received information on the nature of scientific arguments. All students were classified epistemologically as relativists, multiplists, or evaluativists. We found that students in the treatment group incorporated more scientific criteria into their discussion notes and accordingly developed better arguments on several dimensions. In addition, significantly more participants in the treatment group adopted the correct answer to one of the problems. Outcomes also differed in relation to students' epistemic beliefs. Specifically, multiplists were less critical of inconsistencies and misconceptions, and interacted with their partners less than other belief groups, whereas evaluativists interacted more critically, bringing up different ideas from their partners. Evaluativists also solved one of the physics problems more accurately and tended to demonstrate a reduction in misconceptions. We discuss the results in light of instruction in scientific argumentation, conceptual development and change, and epistemic beliefs. (Contains 4 tables.)