Early prediction of sepsis can facilitate early intervention and lead to improved clinical outcomes. However, for early prediction models to be clinically useful, and also to reduce alarm fatigue, detection of sepsis needs to be timely with respect to onset, being neither too late nor too early. In this paper, we propose a utility-based loss function for training early prediction models, where utility is defined by a function according to when the predictions are made and in relation to onset as well as to specified early, optimal and late time points. Two versions of the utility-based loss function are evaluated and compared to a cross-entropy loss baseline. Experimental results, using real clinical data from electronic health records, show that incorporating the utility-based loss function leads to superior multimodal early prediction models, detecting sepsis both more accurately and more timely. We argue that improving the timeliness of early prediction models is important for increasing their utility and acceptance in a clinical setting.