Today the challenge in paternity testing is to provide an accurate noninvasive assay that can be performed early during pregnancy. This requires the use of novel analytical methods capable of detecting the low fraction of circulating fetal DNA in maternal blood. We previously showed that forensic compound markers such as deletion/insertion polymorphisms-short tandem repeats (DIP-STR) can efficiently resolve complex mixed biological evidence including the target analysis of paternally inherited fetal alleles. In this study, we describe for the first time the validation of this type of markers in the first trimester of pregnancies, in addition to defining the statistical framework to evaluate paternity. To do so, we studied 47 DIP-STRs in 87 cases, with blood samples collected throughout gestation starting from the seven weeks of amenorrhea. Fetal DNA detection in the first trimester shows a false negative rate as low as 6%. The combined paternity index (CPI) results indicate that seven markers with fully informative genotypes are sufficient to determine the paternity. This study demonstrates that DIP-STR markers can be used from early pregnancy and that a small set of markers (about 40) is sufficient to address the question of paternity. The novel method offers substantial improvements over similar approaches in terms of reduced number of markers, lower costs and increased accuracy.