Data stream mining has become an emerging research topic in the data mining field, and finding frequent itemsets is an important task in data stream mining with wide applications. Recently, utility mining is receiving extensive attentions with two issues reconsidered: First, the utility (e.g., profit) of each item may be different in real applications; second, the frequent itemsets might not produce the highest utility. In this paper, we propose a novel algorithm named GUIDE (Generation of temporal maximal Utility Itemsets from Data strEams) which can find temporal maximal utility itemsets from data streams. A novel data structure, namely, TMUI-tree (Temporal Maximal Utility Itemset tree), is also proposed for efficiently capturing the utility of each itemset with one-time scanning. The main contributions of this paper are as follows: 1) GUIDE is the first one-pass utility-based algorithm for mining temporal maximal utility itemsets from data streams, and 2) TMUI-tree is efficient and easy to maintain. The experimental results show that our approach outperforms other existing utility mining algorithms like Two-Phase algorithm under the data stream environments.