In one of his blog posts, Alistair Cockburn mentiones his preference of Use Cases over User Stories. He makes some very convincing arguments about why Use Cases are better - user stories don't set a context to work from, teams don't get a sense of completeness of the system, and user stories don't indicate difficulty of upcoming work. I agree with the assessment to a large extent. However, I beg to differ on the case that is being made for Use Cases. Use Cases are dispensable. A set of well written stories is all you need to get a picture of what's to be built and where we are in a project. A format that user story proponents have found very useful is the 'As a ......... I Want To...... So That .........' e.g.
As A Registered GMail User
I Want To change my email sender name to accomodate special characters
So That the name can be displayed in my native language.
A collection of such stories is very useful in portraying a picture of what is to be done and the business value it will deliver. Such stories typically stem from scenarios that emerge out of conversations with the end users, business, and product owners. Some folks also call them epics. These epics or scenarios, in other words, have constituent stories. A collection of such scenarios makes a system. I struggle to see why this is not enough to set context and assess completeness.
The benefit we derive not using Use Cases is the speed with which such scenarios can be constructed and the flexibility of verbiage. Yet another interesting aspect is around the politics of Use Cases. It is not uncommon to find careers built on them. Use case modelers, as they are typically called, have managed to introduced a layer of seemingly very complex set of activities that struggle to keep pace with the change in requirements. This causes nothing but delays.
For a better clarity of relationships between user stories and scenarios, I encourage you to read this.