It depends. If you are working alone, try different approaches and take what works best for you.
Disclaimer: There are a lot of methodologies how to write them up. "User stories" have a very common definition whereas "Use cases" can have very different meanings. I refer to the classical UML diagrams, which are very common.
User stories or Use cases
In my experience, there are different mind sets on which way is the better to understand. So I would decide on every new project team, how to document the requirements. Usually a combination is common, using Use cases for the overview and user stories for details.
- Use cases, especially as diagrams, are better suited for people thinking visually
- User stories are preferred by people thinking in discussiondiscussions who are very talkative
(this is opinion based, without scientific foundation)
What to do first?
On writing the requirements for a project, I would start on a very abstract level. Using use cases, you would paint an (UML-)diagram with the global goals of the project. With user stories, write down a few "epic stories" describing the main goals.
A second step would be to get into the details. Doing this, you should try to keep a reference to an "epic story" or a global goal. This helps structuring the requirements a lot.