High-speed broadband networks will enable public-safety organizations to handle critical situations that go beyond the common voice communication channel. In this paper, we present a user-centered approach that makes the deployment and adoption of next-generation user interfaces reflect the first responders' needs, requirements, and contexts of use. It is composed of four phases where we elicit requirements, iteratively prototype user interfaces, and evaluate our designs. In this process, public-safety organizations are always engaged, contributing through their feedback and evaluation. We will use immersive Virtual Reality to simulate the user interface designs. Within the virtual environment, it is possible to prototype several concepts before committing to a definitive interface. The solutions proposed will be instrumental for the adoption of next-generation user interfaces by the public safety community.