An optimal design theory for structures implemented with tuned mass dampers (TMDs) is proposed in this paper. Full states of the dynamic system of multiple-degree-of-freedom (MDOF) structures, multiple TMDs (MTMDs) installed at different stories of the building, and the power spectral density (PSD) function of environmental disturbances are taken into account. This proposed method allows for a more extensive application and successfully releases the limitations based on simplified models. The optimal design parameters of TMDs in terms of the damping coefficients and spring constants corresponding to each TMD are determined through minimizing a performance index of structural responses defined in the frequency domain. Moreover, a numerical method is also proposed for searching for the optimal design parameters of MTMDs in a systematic fashion such that the numerical solutions converge monotonically and effectively toward the exact solutions as the number of iterations increases. The feasibility of the proposed optimal design theory is verified by using a SDOF structure with a single TMD (STMD), a five-DOF structure with two TMDs, and a ten-DOF structure with a STMD.