Binary relations, in particular, equivalence relations play an important role in both mathematics and information sciences. The concept of soft sets was initiated by Molodtsov as a general mathematical framework for dealing with uncertainty. The present paper establishes a possible connection between binary relations and soft sets. The concept of soft binary relations is introduced and some related properties are investigated. It is shown that any fuzzy relation may be considered as a soft binary relation. Moreover, we discuss the application of soft binary relations in semigroup theory. We consider soft congruence relations over semigroups and show that all soft congruence relations over a semigroup with a fixed parameter set form a lattice. Finally, the notion of soft homomorphisms is presented and isomorphism theorems for soft semigroups are established based on soft congruence relations.