Before you write any code, start by brainstorming all the scenarios you’ll need to cover to make the story done. Do this collaboratively with everyone (devs, testers, UX, business people, product owner) who is interested in the story. Don’t try to make them valid Cucumber scenarios, just make a list of them on a whiteboard, index cards, or in a text file.
Now look at all the scenarios you have. Does the product owner really want you to build the product to satisfy all of them? Can you cut any out and defer them as another story to build later? Can you drop any of them altogether? Get rid of as many as you can until the story is as small as you can make it.
Now count how many scenarios you have left, and write that number on the story card. At the end of the iteration, count up how many scenarios you’re managed to deliver in total across all the stories you’ve done, and start using that as your velocity metric. It’s much, much more accurate in my experience than estimated story points. What’s more, the process of exploring the scenarios means you can agree a clear scope for the story before you get started.
Teams who are doing this well are getting things done much more quickly than they did before. Not only do they build a suite of automated regression tests, but they waste a lot less time writing the wrong code because of misunderstood requirements.