As their name suggests, the Dark Brotherhood has a history shrouded in obfuscation. Their ways are secret to those who are not themselves Brothers of the Order ("Brother" is a generic term; some of their deadliest assassins are female, but they are often called Brothers as well). How they continue to exist in shadow, but be easily found by those desperate enough to pay for their services, is not the least of the mysteries surrounding them.
The Dark Brotherhood sprang from a religious order, the Morag Tong, during the Second Era. The Morag Tong were worshippers of the Daedra spirit Mephala, who encouraged them to commit ritual murders. In their early years, they were as disorganized as only obscure cultists could be—there was no one to lead the band, and as a group they dared not murder anybody of any importance. This changed with the rise of the Night Mother.
All leaders of the Morag Tong, and then afterward the Dark Brotherhood, have been called the Night Mother. Whether the same woman (if it is even a woman) has commanded the Dark Brotherhood since the Second Era is unknown. What is believed is that the original Night Mother developed an important doctrine of the Morag Tong—the belief that, while Mephala does grow stronger with every murder committed in her name, certain murders were better than others. Murders that came from hate pleased Mephala more than murders committed because of greed. Murders of great men and women pleased Mephala more than murders of relative unknowns.
We can approximate the time this belief was adopted with the first known murder committed by the Morag Tong. In the year 324 of the Second Era, the Potentate Versidue-Shaie was murdered in his palace in what is today the Elsweyr kingdom of Senchal. In a brash move, the Night Mother announced the identity of the murderers by painting "MORAG TONG" on the walls in the Potentate's own blood.
Previous to that, the Morag Tong existed in relative peace, more or less like a witches' coven—occasionally persecuted but usually ignored. In remarkable synchronicity at a time when Tamriel the Arena was a fractured land, the Morag Tong was outlawed throughout the continent. Every sovereign gave the cult's elimination his highest priority. Nothing more was officially heard of them for a hundred years.
It is more difficult to date the era when the Morag Tong re-emerged as the Dark Brotherhood, especially as other guilds of assassins have sporadically appeared throughout the history of Tamriel. The first mention of the Dark Brotherhood that I have found is from the journals of the Blood Queen Arlimahera of Hegathe. She spoke of slaying her enemies by her own hand, or if necessary "with the help of the Night Mother and her Dark Brotherhood, the secret arsenal my family has employed since my grandfather's time." Arlimahera wrote this in 2E 412, so one can surmise that the Dark Brotherhood had been in existence since at least 360 if her grandfather had truly made use of them.
The important distinction between the Dark Brotherhood and the Morag Tong was that the Brotherhood was a business as much as it was a cult. Rulers and wealthy merchants used the order as an assassin's guild. The Brotherhood gained the obvious rewards of a profitable enterprise, as well as the secondary benefit that rulers could no longer actively persecute them: They were needed. They were purveyors of an essential commodity. Even an extremely virtuous leader would be unwise to mistreat the Brotherhood.
Not long after Alimahera's journal entry came perhaps the most famous series of executions in the history of the Dark Brotherhood. The Akaviri Emperor-Potentate Savirien-Chorak and every one of his heirs were murdered on one bloody night in Sun's Dawn in 430. Within a fortnight, the Akaviri Potentate crumbled, to the delight of its enemies.
The Dark Brotherhood has no shortage of business opportunities—an "accounting," I have been informed, is the Brotherhood's favorite euphemism for an execution. While they are officially considered an unlawful organization in every corner of the Empire, like the Thieves Guild, they are almost as universally tolerated.