Optimal control of large-scale uncertain dynamic systems with time delays in states is considered in this paper. For this purpose, a two-level strategy is proposed to decompose the large-scale system into several interconnected subsystems at the first level. Then optimal control inputs are obtained by minimization of convex performance indices in presence of uncertainties, in the form of states and interactions feedback. The solution is achieved by bounded data uncertainty problems, where the uncertainties are only needed to be bounded and it is not required to satisfy the so-called ‘matching conditions’. At the second level, a simple substitution-type interaction prediction method is used to update the interaction parameters between subsystems. An iterative two-level algorithm is proposed to coordinate their solutions and achieve the optimal solution of the overall large-scale system. Applicability and performance of the proposed algorithm is shown through simulation of a two coupled inverted pendulums.