Spin caloritronics studies the interplay between charge-, heat- and spin-currents, which are initiated by temperature gradients in magnetic nanostructures. A plethora of new phenomena has been discovered that promises, e.g., to make wasted heat in electronic devices useable or to provide new read-out mechanisms for information. However, only few materials have been studied so far with Seebeck voltages of only some microvolt, which hampers applications. Here, we demonstrate that half-metallic Heusler compounds are hot candidates for enhancing spin-dependent thermoelectric effects. This becomes evident when considering the asymmetry of the spin-split density of electronic states around the Fermi level that determines the spin-dependent thermoelectric transport in magnetic tunnel junctions. We identify Co2FeAl and Co2FeSi Heusler compounds as ideal due to their energy gaps in the minority density of states, and demonstrate devices with substantially larger Seebeck voltages and tunnel magneto-Seebeck effect ratios than the commonly used Co-Fe-B-based junctions.