Mobile Stroke Units (MSUs), which are specialised ambulances equipped with brain imaging devices and trained medical personnel, offer the potential for rapid on-site diagnosis and treatment, improving patient outcomes in prehospital stroke care. To fully realise their benefits, it is essential to strategically allocate. However, identifying optimal locations within a region for MSU deployment is typically computationally challenging due to the vast number of possible combinations of ambulance stations. Existing methods suffer from computational inefficiency, as they consider the whole search space when looking for the optimal solution to the MSU allocation problem. In the current paper, we propose a framework, Quality Clustering for Reducing the Search Space (QCRSS), which uses clustering as a preprocessing step to significantly reduce the number of candidate MSU locations while maintaining high solution quality for the MSU allocation problem. In a real-world use case study, we evaluate our proposed framework in Sweden’s southern healthcare region. Extensive experiments across multiple MSU settings demonstrate that QCRSS achieves the optimal solution for two, three, and four MSUs, and a highly satisfactory solution even for the larger and more complex case of five MSUs. The proposed framework reduces the search space by 5x, 11x, 26x, and 67x and for two, three, four, and five MSUs, respectively. We illustrate the performance of QCRSS through both qualitative and quantitative analyses.