We have used previously published observations of the CO emission from the Antennae (NGC 4038/39) to study the detailed properties of the super giant molecular complexes with the goal of understanding the formation of young massive star clusters. Over a mass range from 5E6 to 9E8 solar masses, the molecular complexes follow a power-law mass function with a slope of -1.4 +/- 0.1, which is very similar to the slope seen at lower masses in molecular clouds and cloud cores in the Galaxy. Compared to the spiral galaxy M51, which has a similar surface density and total mass of molecular gas, the Antennae contain clouds that are an order of magnitude more massive. Many of the youngest star clusters lie in the gas-rich overlap region, where extinctions as high as Av~100 imply that the clusters must lie in front of the gas. Combining data on the young clusters, thermal and nonthermal radio sources, and the molecular gas suggests that young massive clusters could have formed at a constant rate in the Antennae over the last 160 Myr and that sufficient gas exists to sustain this cluster formation rate well into the future. However, this conclusion requires that a very high fraction of the massive clusters that form initially in the Antennae do not survive as long as 100 Myr. Finally, we compare our data with two models for massive star cluster formation and conclude that the model where young massive star clusters form from dense cores within the observed super giant molecular complexes is most consistent with our current understanding of this merging system. (abbreviated)