We develop some of the ingredients needed for string theory on noncommutative spacetimes, proposing an axiomatic formulation of T-duality as well as establishing a very general formula for D-brane charges. This formula is closely related to a noncommutative Grothendieck-Riemann-Roch theorem that is proved here. Our approach relies on a very general form of Poincaré duality, which is studied here in detail. Among the technical tools employed are calculations with iterated products in bivariant K -theory and cyclic theory, which are simplified using a novel diagram calculus reminiscent of Feynman diagrams. © 2007 Springer-Verlag.