My best example is my great-grandmother's mother. I knew her name and had a treasured family photo from 1888 of her with her father and sisters, her marriage record (an original handwritten copy, even), her husband's Bible stating her death date, and a family story that she had maybe been born in Mississippi. Sounds like a good start, but she died young and before the 1900 census, and the 3rd then the 4th wife raised her infant children, and any memory of her faded quickly. No death record, no succession record, no newspaper record, no cemetery record, no way to reasonably narrow down the 1880 census due to her common name, no known relatives, etc.
Because of a moderate-to-low (I forget which) DNA match here, and because it was the early days of the test when I had time to look carefully at every single match (all 200 of them back then, lol), I considered whether this DNA match's family with the same surname could be related to my family with that name. As I looked at this match's records, my ancestor seemed to fit very well with a daughter about whom nothing was known (by this researcher).
If I had diligently researched every family with this surname in mid-1800s Mississippi forward through all lines (in a situation of all daughters who married and changed their names), then I suppose *technically* I would have had the same light bulb go off as when I saw this match in my DNA list, but I think undertaking that task would have been an unrealistic expectation. I like to work collateral lines into the ground and chase all kinds of theories, but I don't have time to develop a well-sourced genealogy of everyone with a somewhat common surname in an entire state (which may not have even been where my ancestor was from).
When my Dad tested here, the same match came up as a high confidence match (3rd cousin), plus Dad had other matches here and at FTDNA to people who descended from these theoretical ancestors. When my great-aunt tested, she got the 3rd cousin match plus a 2nd cousin match who descends from what are her theoretical great-grandparents. She also has other matches related to this couple that my Dad didn't get, and a few of them seem willing to join GEDmatch, so I'm pretty excited that in won't be long before I can't cite specific matching segments as evidence.
If I'd researched exclusively with paper, which again would have taken years if not decades if I'd hoped to do other things in life as well, I'd at best have had an interesting theory with a few too many "could be coincidence" thoughts nagging at me to ever accept it to the point where I'd add these names to my family tree. DNA has definitely sealed the deal for me here.
That's just my best and brightest example. I now have had many experiences where the documentation was shaky but - thanks to several matches on the same segment - I'm now confident in the connection. I also have more theories/family stories without known documentation that are starting to look promising as a result of DNA.
The breakthroughs depend on luck: who else tests and what they put in their tree. My husband, who is not American (and thus tested at FTDNA due to the more international database), has not found a single identifiable cousin. He has a couple of really close matches, but they haven't responded. Bad luck. But me, I had my biggest brick wall break down because of autosomal DNA testing. (And my second biggest is crumbling due to yDNA testing.) It's all pretty amazing and is only going to get better.