An asynchronous time difference of arrival (ATDOA) positioning system requires no time synchronization among all the anchor and target nodes, which makes it highly practical and can be easily deployed. This paper first presents an ATDOA localization model, and then primarily focuses on two new localization algorithms for the system. The first algorithm is a two-step positioning algorithm that combines semidefinite programming (SDP) with a Taylor series method to achieve global convergence as well as superior estimation accuracy, and the second algorithm is a constrained least-squares method that has the advantage of low complexity and fast convergence while maintaining good performance. In addition, a novel receiver re-selection method is presented to significantly improve estimation accuracy. In this paper, we also derive the Cramer-Rao lower bound (CRLB) of the ATDOA positioning system using a distance-dependent noise variance model, which describes a realistic indoor propagation channel.