Abstract This study formulates the design of optimal observing networks for past surface climate conditions as the solution to a data assimilation problem, given a realistic proxy system model (PSM), paleoclimate observational uncertainties, and a network of current and proposed observing sites. The method is illustrated with the design of optimal networks of coral δ18O records, chosen among candidate sites, and used to jointly infer sea surface temperature (SST) and sea surface salinity (SSS) fields from the Community Climate System Model, version 4, last millennium simulation over the 1850–2005 period. It is shown that an existing paleo-observing network accounts for approximately 20% of the SST variance, and that adding 25 to 100 optimal pseudocoral sites would boost this fraction to 35%–52%. Characterizing the SST variance alone, or jointly with the SSS, leads to similar optimal networks, which justifies using coral δ18O records for SST reconstructions. In contrast, the network design for reconstructing SSS alone is fundamentally different, emphasizing the hydroclimatic centers of action of El Niño–Southern Oscillation. In all cases, network design depends strongly on the amplitude of the observational error, so replicates may be more beneficial than the exploration of new sites; these replicates tend to be chosen where proxies are already informative of the large-scale climate field(s). Finally, extensions to other types of paleoclimatic observations are discussed, and a path to operationalization is outlined.