Integrated circuit packages with stripline structures are provided. An integrated circuit package substrate may include a core layer having top and bottom surfaces and dielectric layers formed on the top and bottom surfaces of the core layer. Stripline structures may be formed in at least some of the dielectric layers. A stripline trace may include signal routing conductors sandwiched between top and bottom ground planes. In particular, a dielectric layer may be formed between the signal conductors and the bottom ground plane to support the signal conductors, whereas a localized air region may be formed over the signal routing conductors separating the signal conductors from the top ground plane. If desired, the region above the signal routing conductors between the top ground plane and the signal routing conductors may be filled using other types of material having low loss and/or a dielectric constant that is frequency independent.