Tl;dr;
Do relative sizing on features.
To Elaborate:
When you’re looking at a fixed-bid contract, you’re saying “It will take me no more than this much money to do deliver the full scope.”
This is problematic in Agile because we recognize that most software projects do not understand their scope until very late in the project. This isn’t the result of Agile – most waterfall projects don’t understand their scope either; the difference is that Agile doesn’t pretend to.
Feature Sizes
When we look at the overall size of a project, we still want to use relative sizing. You may have a baseline feature from past projects (you always have to start with something you’ve really done) and that may be a medium. Then you can look at features on new projects and ask “Is that about the same size, a little larger, a lot smaller?” Your development group will have a velocity at this level just like it does at the sprint level.
If your team has an average sprint velocity of around 30 story points and you have 3 8-point stories and 4 5-point stories, they’ll probably complete those in 2 sprints. The feature sizes work the same way. Medium features (if you’re doing relative sizing properly) will cost around the same with a certain margin of error.
Why Not Just Add Story Points?
If you detail out all of the stories and estimate them all, you assume that the scope is fixed and you thoroughly understand that. As soon as you assume that, you’re taking on incredible risk to yourself and your client and defeating many of the core principles of agile.
By looking at feature size and applying relative estimation there, you’re leaving plenty of room for uncertainty and modifications to the details.
How Can You Start?
Look at your past work. Apart from using a past feature as a baseline, you can also retroactively do some relative estimation to give you a base of data to work with. There’s a big pitfall here though: you know how long it took – you’ll naturally want to use reality to influence your estimates. You can try to consciously avoid this or maybe have people do the relative estimation who didn’t work on the feature.
Be Warned
Just like the way messing with team composition throws story point velocity off and story points aren’t comparable between groups, if you constantly change up your development group’s structure or split people on projects, this approach will fall apart and you will not be able to see trends in feature cost.