Le 16 janvier 2009, Hollins a été échangé aux Mavericks de Dallas avec DeSagana Diop, en échange de Matt Carroll.
Le 16 janvier 2009, Hollins a été échangé avec Matt Carroll en échange de DeSagana Diop contre les Mavericks de Dallas.