Bitumen-clay nanocomposite binders with styrene-butadienestyrene triblock copolymer, SBS, and combinations of SBS and crumb rubber (CR) with different CR/SBS ratios have been synthesized and characterized. In addition to the binder, samples containing the binder and concrete sand (with a weight ratio 1:9) were prepared. The modified binders were studied in terms of filler dispersion, storage stability, mechanical performance and water susceptibility. We demonstrate that the samples containing nanoclays consistently outperform those based only on the polymer additives. We also find that nanocomposite samples based on a combination of SBS and CR are best, since in addition to other improvements they show excellent storage stability. Our work shows that substituting CR with SBS as a bitumen additive and combining it with inexpensive nanoclays leads to new materials with enhanced performance and improved stability for practical asphalt applications.