A method and apparatus to find maximal frequent itemsets over data streams. A prefix tree manages itemsets and appearance frequencies of the itemsets, and each of nodes of the prefix tree has information about an appearance frequency, a maximum lifetime, and a mark indicating whether the corresponding itemset is a maximal frequent itemset. The method includes: receiving transaction Tk generated at a current point in time; updating the information owned by each node corresponding to the itemset of the transaction Tk among the nodes of the prefix tree; adding each node that is not managed in the prefix tree among nodes corresponding to the itemset of the transaction Tk, to the prefix tree and setting the information on the added nodes; and finding maximal frequent itemsets by visiting each node of the prefix tree that has the mark indicating the maximal frequent itemset and checking whether the corresponding itemset is frequent.