We give an explicitly computable lower bound for the arithmetic self-intersection number (omega) over bar (2) of the dualizing sheaf on a large class of arithmetic surfaces. If some technical conditions are satisfied, then this lower bound is positive. In particular, these technical conditions are always satisfied for minimal arithmetic surfaces with simple multiplicities and at least one reducible fiber, but we also use our techniques to obtain lower bounds for some arithmetic surfaces with non-reduced fibers.