Uncertainty is ubiquitous in natural human communication. Human listeners assess the speaker's degree of uncertainty at any time in communication and use this information to shape dialogue. In contrast, currently available computer systems dealing with spoken language are usually not built to perform this task. The ability to detect uncertainty would likely lead to more natural human-computer dialogue. In order to detect uncertainty automatically, we extract linguistic, paralinguistic and dialogue-related features from the Kiel Corpus, a corpus of naturalistic task-oriented spoken German. We then use these features to train a random forests model. Our experimental results show that relatively high classification accuracy can be obtained while employing only 64 well-chosen features (73% accuracy, 69% F1). To our best knowledge, this is the first study of automatic uncertainty detection using German speech data as well as the first achieving good performance on everyday speech.