We investigate the influence of the fluid constitutive model on the outcome of shape optimization tasks, motivated by optimal design problems in biomedical engineering. Our computations are based on the Navier-Stokes equations generalized to non-Newtonian fluid, with the modified Cross model employed to account for the shear-thinning behavior of blood. The generalized Newtonian treatment exhibits striking differences in the velocity field for smaller shear rates. We apply sensitivity-based optimization procedure to a flow through an idealized arterial graft. For this problem we study the influence of the inflow velocity, and thus the shear rate. Furthermore, we introduce an additional factor in the form of a geometric parameter, and study its effect on the optimal shape obtained.