In recent years underwater survey and surveillance missions with more than a single Autonomous Underwater Vehicle (AUV) have become more common thanks to more reliable and cheaper platforms, as well as the addition of remote command and control communications using, for example, the WHOI acoustic modem. However cooperative navigation of AUVs has thus far been limited to a single AUV supported by a dedicated surface vehicle with access to GPS. In this paper a scalable and modular framework is presented in which any number of vehicles can broadcast, forward and acknowledge range, dead-reckoning, feature and GPS measurements so that the full fleet of AUVs can navigate and cooperate in a consistent and accurate manner. The approach is independent of the resultant application—such as recursive state estimation or full pose optimization. Trade-offs between the number of vehicles, the condition of the communication channel and rate at which updates are available are also discussed. Finally performance is illustrated in a realistic experiment.