We present preliminary results from a new HST archival program aimed at tightly constraining the ancient (>4 Gyr ago) star formation histories (SFHs) of the field populations of the SMC and LMC. We demonstrate the quality of the archival data by constructing HST/WFPC2-based color-magnitude diagrams (CMDs; M_{F555W} ~ +8) for 7 spatially diverse fields in the SMC and 8 fields in the LMC. The HST-based CMDs are >2 magnitudes deeper than any from ground based observations, and are particularly superior in high surface brightness regions, e.g., the LMC bar, which contain a significant fraction of star formation and are crowding limited from ground based observations. To minimize systematic uncertainties, we derive the SFH of each field using an identical maximum likelihood CMD fitting technique. We then compute an approximate mass weighted average SFH for each galaxy. We find that both galaxies lack a dominant burst of early star formation, which suggests either a suppression or an under-fueling of early star formation. From 10-12 Gyr ago, the LMC experienced a period of enhanced stellar mass growth relative to the SMC. Similar to some previous studies, we find two notable peaks in the SFH of the SMC at ~4.5 and 9 Gyr ago, which could be due to repeated close passages with the LMC, implying an interaction history that has persisted for at least 9 Gyr. We find little evidence for strong periodic behavior in the lifetime SFHs of both MCs, suggesting that repeated encounters with the Milky Way are unlikely. Beginning ~3.5 Gyr ago, both galaxies show increases in their SFHs, in agreement with previous studies, and thereafter, track each other remarkably well. (abridged)