We consider a Bolza-type optimal control problem for a dynamical system described by a fractional differential equation with the Caputo derivative of an order alpha is an element of (0, 1). The value of this problem is introduced as a functional in a suitable space of histories of motions. We prove that this functional satisfies the dynamic programming principle. Based on a new notion of coinvariant derivatives of the order alpha, we associate the considered optimal control problem with a Hamilton-Jacobi-Bellman equation. Under certain smoothness assumptions, we establish a connection between the value functional and a solution to this equation. Moreover, we propose a way of constructing optimal feedback controls. The paper concludes with an example.