We investigate how Murray's law is affected by fluids whose viscosity depends monotonously on shear rates, such as blood. Our study shows that Murray's original law also applies to such fluids, as long as they did not undergo phase separation effect. When Fahraeus-like phase separation effects occur, we derive an extended version of Murray's law. Finally, we study how these new laws affect the optimal geometries of fractal trees to mimic an idealized arterial network. Our analyses are based on Quemada's fluid model, but our approach is very general and applied to most fluids with shear dependent rheology. (C) 2015 The Society of Rheology.