A spatial optimization model was developed for deploying, over the next two decades, hydrogen refueling stations for heavy-duty zero-emission hydrogen vehicles. The model assigns trips to vehicles by applying a routing algorithm to travel demand data derived from another model—the California Statewide Travel Demand Model (developed by the California Department of Transportation). Across a range of adoption levels of hydrogen fuel-cell truck technology, from 2020 through 2030, the results suggest that heterogeneity of travel demand may necessitate an extensive distribution of refueling stations, which may lead to low utilization of stations in the short term. To efficiently employ the capacity of stations, a certain volume of vehicle adoption must be met, and/or truck routes must be planned and committed to specific roadways. Once the number of stations reaches a threshold to meet the principal demand in affected transportation area zones, a small set of smaller “top-off” stations can be built to meet marginal excess demand. The best location of a hydrogen refueling station within a transportation area zone also depends on the criteria such as land cover, slope, and distance from gas stations, truck hubs, and the truck network.