Complex Finsler vector bundles have been studied mainly by T. Aikou, who defined complex Finsler structures on holomorphic vector bundles. In this paper, we consider the more general case of a holomorphic Lie algebroid $E$ and we introduce Finsler structures, partial and Chern-Finsler connections on it. First, we recall some basic notions on holomorphic Lie algebroids. Then, using an idea from E. Martinez, we introduce the concept of complexified prolongation of such an algebroid. Also, we study nonlinear and linear connections on the tangent bundle $T_{\mathbb{C}}E$ and on the prolongation $\mathcal{T}_{\mathbb{C}}E$ and we investigate the relation between their coefficients. The analogue of the classical Chern-Finsler connection is defined and studied in the paper for the case of the holomorphic Lie algebroid $E$.