Stroke is the second leading cause of death worldwide, and the time to treatment is the most important factor to increase the chances of desirable recovery. To ensure proper treatment of stroke patients, a diagnosis must first be made to ensure that the correct treatment is provided. This requires a computed tomography scan, which traditionally necessitates transporting the patient to an acute hospital. To reduce the time to treatment, so-called Mobile Stroke Units (MSUs) have been introduced. A mobile stroke unit is a specialized ambulance where stroke patients can be diagnosed and provided with certain types of treatment. For many stroke patients, the use of mobile stroke units can lead to reduced time to treatment improving their chances of recovery. However, mobile stroke units are very expensive, making it important to locate them in a way that maximizes their benefit. In the current paper, we apply Multi-State Particle Swarm Optimization (MS-PSO) to solve the problem of identifying optimal locations for mobile stroke units in a geographical region. To illustrate our method, we applied it to allocate three mobile stroke units in Sweden’s southern health care region. The objective was to find mobile stroke unit locations to maximize the share of the population that is expected to receive treatment within 1 h. For the best-found solution, about 81% of the population is expected to receive treatment within 1 h.