Abstract Classical constraint satisfaction problems (CSPs) are commonly de?ned on ?nite domains. In real life, constrained variables can evolve over time. A variable can actually take an in?nite sequence of values over discrete time points. In this paper, we propose constraint programming on in?nite data streams, which provides a natural way to model constrained time-varying problems. In our framework, variable domains are speci?ed by ?-regular languages. We introduce special stream operators as basis to form stream expressions and constraints. Stream CSPs have in?nite search space. We propose a search procedure that can recognize and avoid in?nite search over duplicate search space. The solution set of a stream CSP can be represented by a Bu?chi automaton allowing stream values to be non-periodic. Consistency notions are de?ned to reduce the search space early. We illustrate the feasibility of the framework by examples and experiments.