Wordorigins.org

Brothel derives, through the Middle English broþel, from the Old English bréoðan, meaning ruined or degenerate. It is a variant of the word brethel, meaning a good-for-nothing, a wretch.

The original sense was of a worthless or degenerate person and first appears in William Langland’s Piers Plowman, A text, which was written c.1367-70, with the surviving manuscripts dating to c.1390:

For nou is vche Boye, Bold Broþel, an[d?] oþer, To talken of þe Trinite, to beon holden A syre.
(For now is each boy (commoner), bold brothel, and other, to talk of the Trinity, to be looked upon as a sire.)