We study twisted $Spin^c$-manifolds over a paracompact Hausdorff space $X$ with a twisting $\alpha: X \to K(\ZZ, 3)$. We introduce the topological index and the analytical index on the bordism group of $\alpha$-twisted $Spin^c$-manifolds over $(X, \alpha)$, taking values in topological twisted K-homology and analytical twisted K-homology respectively. The main result of this paper is to establish the equality between the topological index and the analytical index. We also define a notion of geometric twisted K-homology, whose cycles are geometric cycles of $(X, \a)$ analogous to Baum-Douglas's geometric cycles. As an application of our twisted index theorem, we discuss the twisted longitudinal index theorem for a foliated manifold $(X, F)$ with a twisting $\alpha: X \to K(\ZZ, 3)$, which generalizes the Connes-Skandalis index theorem for foliations and the Atiyah-Singer families index theorem to twisted cases.