Break it down into high-level epics. Take each functional area of the application, one step at a time.

Break one epic down into a group of stories (usable chunks — anything that improves the application) and manage those as you would if you didn’t have an existing application, with one exception: If it is possible, make it so that you can implement that one piece of functionality as part of, or alongside, the original application.

When Agilists say “release early and often”, that doesn’t necessarily mean to production. If you’re going to replace an existing application, you should use a staging area to release often, and make sure your users are testing the system there. This will still give them room to prioritise the next piece of work and to make sure that nothing you release to production depreciates the product.

Once you’ve released one component to production, move onto the next.

we just got through such an experience (me as scrum product owner). It took us two years to get to something releasable. But still, agile brought us many benefits.

First: A total rewrite is by nature not agile at all. You should instead consider refactoring the existing product piece by piece. That has been discussed in another question. So let’s assume it has to be a rewrite.

Then indeed, you start with a back log that covers all the relevant use cases of the existing product. But please don’t approach it as writing specs. That would be too much detail. It should be complete (otherwise you can’t do release planning). And it shouldn’t be too elaborate (otherwise you’re writing specs upfront). Here’s how we approached that:

• categorize the users of the old product. Identify the users that only need a small part of the old product and still get something useful out of it. They define your first epics.

• Then add epics that would allow another category of users to move to the new product. Etc. until you have a back log that covers all users.

• most likely, these epics will need further splitting. If possible, try to split so that each part still has some value. If that’s not feasible, then at least make sure each part can be demonstrated.

• when you have 20-50 epics, have the team estimate them.

• split the top most epics into User Stories that the team believes to be feasible within a sprint. Don’t do that for all epics yet, only the ones on top. You’ll have plenty of time for splitting the rest.

When to release externally! That is a business decision. At least this approach gives you the opportunity to release earlier to certain user categories. That can be handy if management gets nervous about this seemingly never ending project.

Release Now If You Can

Your question about when do you start releasing the code is a great one. I think that two provisos apply. First, that you have “good enough quality”, and second that that you meet the requirements for an MVP (minimum viable product).

Rome (and Agile) Weren’t Built in a Day

Maybe you are ready with a turnkey agile team to take over on day one. For most organizations, there is the work and expense of training, retooling, and the usual forming, storming, norming, performing cycle of building a team. Be up front about the risks and costs, be careful to set realistic expectations, and be up beat and prepared to advocate your approach.

Be a Reuse Bootstrapper

Like fusion power, code reuse is and always will be the future solution to our economic problems. My feeling is that developers often say they believe in reuse, but only the kind of reuse that starts after they build a new framework, rather than the kind where they build on what someone else has already done. How can that work until someone is willing to chose to build on someone else’s foundation? At best, it means a rewrite every few years when team leadership changes.

Why Release Early And Often?

Release early and often is a mantra for many reasons. It gives life to our discussions about what the product should become, it makes real where we are, and it gives us a base for iterative/incremental changes. The pace of releases is pretty much an invariant for agile, with the difference being who receives the releases (customer surrogates or end users). Before agile, maintenance was estimated to account for 60% of the cost of software systems. This is a source of much consternation for managers and others, some who feel the product release is where software goes to die. For them, everything after the release is rework and paying to fix a product that they paid for once already.

Pre-release is Unnatural

Kent Beck writes that pre-release is an unnatural state for software products. It is certainly an inconvenient time because it is a time when you have no customers and you are paying for the product rather than the product paying for you.

Don’t Criticize the Previous Team

While it might setup the developers who take over the rewrite as the heros and salvation of the project, I think there is a cost to criticizing the previous team’s accomplishments.

• First, if you let people make up their own mind about the previous team, you have more time and energy for your real mission.
• It will be awkward if you need to work with members of the previous team, both developers as well as stakeholders like product managers, project managers, or customers.
• If you can get it working, you may find yourself receiving (or worse yet taking) credit for what the previous team did.
• On average, the previous team was probably average. On average, you might be average. You have more work than the previous team because you have a new methodology to put in place in addition to a project.
• If the old team was horrible, unless you are horrible too, you will eventually get credit for being better than horrible. If they were better than horrible, and you aren’t noticeably better, saying they were horrible may invite unpleasant comparisons.
• If the old team was better than you thought they were, and you get into trouble because the organization is broken or the problem is ill defined or very difficult, things will go better for you if you haven’t significantly raised expectations.
• If they expect what they were getting, but you do better, it is a win for you.
• To refrain from criticism is both good manners, and shows that you have class.

Prompted by the comments by @Chuck and references to Netscape essentially saying don’t rewrite, and valid responses retorting that he OP is not asking if he should. – A truly agile software development cycle precludes rewriting. Rewriting almost always breaks many of the principles behind Agile.
Using the current software as a base-line these Agile principles (from Agile Manifesto) cannot be met with a rewrite.

• Early and continuous delivery of valuable software. – the customer will not get early value when measured against what they already have
• Deliver working software frequently – weeks to months – how big is the project, can you honestly say the customer will get anything more useful to them anytime soon.
• Working software is the primary measure of progress – working compared to the baseline won’t happen in a hurry
• Agile processes promote sustainable development. – Given the customer has a working baseline, the pressure will be on to deliver improved functionality. This is unlikely to be done at a pace that sustainable
• Simplicity–the art of maximizing the amount of work not done–is essential. this Says it all really…

“Suppose you have to rewrite an entire application using Agile
methodologies, how would you do it?”

The question is based on a false premise – That a rewrite can be considered Agile.

Consider whether you can release the rewritten application a piece at a time, and have it in production side by side with the old one.

For web applications in particular, it may be fairly easy to move a single part of the application to a new platform, and have your load balancer route requests to the appropriate system. Then write up the stories that will let you get your first page into production, and deliver those in an agile way.

Desktop applications can be more complicated, but it will often be possible.

You’re looking for seams – places where it is possible for the old system to have its responsibilities taken over by the new, without needing a full rewrite.

Perhaps there is some self-contained business logic that can be moved into a new web service or framework, and the old app can be modified use that instead of its old code. Just keep carving off chunks at the seams until what is left is manageable all in one bite.

If you can’t find any seams, then you may indeed need to look for the kind of big bang approach suggested in some of the other answers. But be prepared for a long march before you reach your destination, especially if you are expected to keep developing the old system in parallel…

Agile says we should release early and often, but it doesn’t make much sense to release
before the complete rewrite has been completed.

Actually, IMHO this is the key point – the earlier you get parts of the rewritten application in production (and ideally replacing functionality of the old system), the bigger the chances are that your project will be sucesssful. If you think this does not much sense, think harder about it – there are almost always possibilities to release parts.

It will probably mean someone has to change something in the old application, for example, add some new interfaces to interact with the rewritten application during the time the rewrite is not complete. But to my experience, such additional work always pays for itself.

Once the first parts of the new application is in production, the agile, iterative approach will become obvious. Requirements will change, your user stories will change or get new priorities, and hopefully you will replace more and more functionality of the old system in small steps.