The story that you implement at the beginning can be refined over time. You dont need to think that every story has to be the final version that the user is going to use.
For example, in a recent project we had to develop an application which involved indexing various websites, and matching them against filters created by users, and finally alerting the user of matches (thing of it as google alert on steroids).
If you look at it from one perspective, there is only one story - "As a user I want to get alerts from matching pages". But look at it from another perspective of "what are the risks we want to mitigate". The first risk was that users wouldn't get relevant or better hits compared to google alerts. The second risk was in learning the technology to build this.
So our first user story was simply "As a user I want relevant hits", then we built just the hit matching algorithm on a hardcoded set of pages and hardcoded filters for some early users and got their feedback.
There might actually be a bit of back and forth here with multiple smaller stories to capture learning like "As a user I want more priority to be given to matches in the URL" etc.. these stories comes from the feedback as we iterate over what the early users consider "relevant hits".
Next, we broadened it to "As a user I want hits from specific websites" and we built the indexing architecture to crawl user specified sites and do hit matching on that.
The third story was "As a user I want to define my own filters", and we built this part of the system.
In this way we were able to build up the architecture piece by piece. Through most of the initial part, only early users could use the system, and many pieces of data were hardcoded etc.
After a point, early users could use the system completely. Then we added stories for allowing new users to register and opened it up to the public.
To cut a long story short, the story you implement first could implement only a small part of the final story, hardcoding and scaffolding everything else. And then you can iterate on it over time till you get the story that you might actually release to the public.