Psammaplin A is a symmetrical bromotyrosine-derived disulfide natural product isolated from the Psammaplysilla sponge, which exhibits in vitro antibacterial activity against methicillin-resistant Staphylococcus aureus (MRSA). Inspired by the structure of this marine natural product, a combinatorial scrambling strategy for the construction of heterodimeric disulfide analogues was developed and applied to the construction of a 3828-membered library starting from 88 homodimeric disulfides. These psammaplin A analogues were screened directly against various gram positive bacterial strains leading to the discovery of a series of potent antibacterial agents active against methicillin-resistant Staphylococcus aureus (MRSA). Among the most active leads derived from these studies are compounds 104, 105, 113, 115, 123, and 128. The present, catalytically-induced, disulfide exchange strategy may be extendable to other types of building blocks bearing thiol groups facilitating the construction of diverse discovery-oriented combinatorial libraries.