A new procedure for the design of clustered array antennas for base stations in multiuser multiple-input-multipleoutput systems is presented. Although formulated as a deterministic optimization problem that does not rely on a specific channel model, this procedure generates array designs that yield enhanced effective gains in various stochastic propagation channels. It comprises two separate parts. In Part I, properties of the individual sub-arrays (SAs) are jointly optimized based on a new gain-based design criterion formulated in the angle domain. This criterion incorporates the embedded element pattern of arbitrary physical antenna elements. In Part II, the array design is finalized by optimizing the relative positions of the SAs resulting from Part I. The proposed design procedure is demonstrated for clustered arrays composed of non-overlapping steered and nonsteered SAs (i.e., tiled arrays) and for both isotropic and dualpolarized patch antenna elements. Simulations are conducted to evaluate the gains provided by the optimized clustered arrays in urban-micro propagation channels. Compared to full-digital arrays comprising the same number of radio frequency chains, the optimized clustered arrays enhance the gain in 61% to 99% of the channel realizations, depending on the SA type and the users' spatial distribution. Average gain enhancements up to 4.9 dB are achieved.