The accuracy of indoor positioning systems could be significantly reduced by non-line-of-sight (NLOS) propagation. The bulk of existing work on NLOS error mitigation for time-of-arrival (TOA) systems assumes that the NLOS links can be identified and/or the NLOS error statistics are known. To avoid requiring such information that is often unavailable in practice, recent work has applied convex optimization for NLOS error mitigation. However, convex optimization for NLOS error mitigation in TOA systems is often an infeasible problem. A strategy to reduce the infeasible problem probability is to relax the constraints for the optimization at the expenses of a reduced positioning accuracy. In this paper, we develop a soft-minimum method for NLOS error mitigation TOA systems. The major advantages of the proposed method include: 1) like existing convex optimization schemes, it does not require any a priori information about NLOS links or NLOS error statistics; 2) unlike existing convex optimization schemes, it does not have infeasibility issues; and 3) it results in a higher positioning accuracy than with existing convex optimization schemes.