Given a set of n colored points \(P \subset \mathbb {R}^d\) we wish to store P such that, given some query region Q, we can efficiently report the colors of the points appearing in the query region, along with their frequencies. This is the color frequency reporting problem. We study the case where query regions Q are axis-aligned boxes or dominance ranges. If Q contains k colors, the main goal is to achieve “strictly output-sensitive” query time \(O(f(n) + k)\) . We show that, for every \(s \in \{2,\dots ,n\}\) , there exists a simple \(O(ns\log _s n)\) -size data structure for points in \(\mathbb {R}^2\) that allows frequency reporting queries in \(O(\log n + k\log _s n)\) time. Furthermore, we give a lower bound for the weighted version of the problem in the arithmetic model, proving that with O(m) space one can not achieve query times better than \(\varOmega \left( \phi \frac{\log (n / \phi )}{\log (2m / n)}\right) \) , where \(\phi \) is the number of possible colors. This means that our data structure is near-optimal. We extend these results to higher dimensions as well. Finally, we give an \(O(n^{1+\varepsilon } + m \log n + K)\) -time algorithm that can answer m dominance queries \(\mathbb {R}^2\) with total output complexity K, while using only linear working space.