Language researchers view utterance planning as implicit decision-making: producers must choose the words, sentence structures, and various other linguistic features to communicate their message. To date, much of the research on utterance planning has focused on situations in which the speaker knows the full message to convey. Less is known about circumstances in which speakers begin utterance planning before they are certain about their message. In three picture-naming experiments, we used a novel paradigm to examine how speakers plan utterances before a full message is known. In Experiments 1 and 2, participants viewed displays showing two pairs of objects, followed by a cue to name one pair. In an Overlap condition, one object appeared in both pairs, providing early information about one of the objects to name. In a Different condition, there was no object overlap. Across both spoken and typed responses, participants tended to name the overlapping target first in the Overlap condition, with shorter initiation latencies compared with other utterances. Experiment 3 used a semantically constraining question to provide early information about the upcoming targets, and participants tended to name the more likely target first in their response. These results suggest that in situations of uncertainty, producers choose word orders that allow them to begin early planning. Producers prioritize message components that are certain to be needed and continue planning the rest when more information becomes available. Given similarities to planning strategies for other goal-directed behaviors, we suggest continuity between decision-making processes in language and other cognitive domains.