Bio-hybrid micro-swimmers, composed of biological entities integrated with synthetic constructs, actively transport cargo by converting chemical energy into mechanical work in a fluid at low Reynolds number, where viscous drag dominates over inertia. Here, using isolated and demembranated flagella from green algae Chlamydomonas reinhardtii ( C. reinhardtii ), we build efficient axonemally-driven micro-swimmers that consume ATP to propel micron-sized beads. Depending on the calcium concentration, we observed two main classes of motion: Whereas beads move along curved trajectories at calcium concentrations below 0.03 mM, they are propelled along straight paths when the calcium concentration increases. In this regime, they reached velocities of approximately 20 μ m/sec, comparable to human sperm velocity in vivo . We relate this transition to the properties of beating axonemes, in particular the reduced static curvature with increasing calcium concentration. To quantify the motion, we used mode decomposition of the flagellar waveform, and we studied both analytically and numerically the propulsion of the bead as a function of the axonemal waveform and bead-axoneme attachment geometry. While our analysis semi-quantitatively describes the experimental results, it also reveals the existence of a counter-intuitive propulsion regime where the speed of the axonemally-driven bead increases with the size of the bead. Moreover, we demonstrated that asymmetric, sideways attachment of the axoneme to the bead can also contribute to the rotational velocity of the micro-swimmer. The uncovered mechanism has potential applications in the fabrication of synthetic micro-swimmers, and in particular, bio-actuated medical micro-robots for targeted drug delivery.