Fees are omnipresent in markets but, with few exceptions, are omitted in economic models—such as Double Auctions—of these markets. Allowing for general fee structures, we show that their impact on incentives and efficiency in large Double Auctions hinges on whether the fees are homogeneous (as, e.g., fixed fees and price fees) or heterogeneous (as, e.g., bid-ask spread fees). Double Auctions with homogeneous fees share the key advantages of Double Auctions without fees: markets with homogeneous fees are asymptotically strategyproof and efficient. We further show that these advantages are preserved even if traders have misspecified beliefs. In contrast, heterogeneous fees lead to complex strategic behavior (price guessing) and may result in severe market failures. Allowing for aggregate uncertainty, we extend these insights to market organizations other than the Double Auction.