We propose a real-time solution for modeling and tracking multiple 3D objects in unknown environments for Augmented Reality. The proposed solution consists of both scalable tracking and interactive modeling. Our contribution is twofold: First, we show how to scale with the number of objects using keyframes. This is done by combining recent techniques for image retrieval and online Structure from Motion, which can be run in parallel. As a result, tracking 50 objects in 3D can be done within 6-35 ms per frame, even under difficult conditions for tracking. Second, we propose a method to let the user add new objects very quickly. The user simply has to select in an image a 2D region lying on the object. A 3D primitive is then fitted to the features within this region, and adjusted to create the object 3D model. We demonstrate the modeling of polygonal and circular-based objects. In practice, this procedure takes less than a minute. (c) 2012 Elsevier Ltd. All rights reserved.