A Noether type symmetry theorem for fractional Birkhoffian systems was proposed. Two new transformation formulas for generalized fractional derivative operators were derived, and thus, the constants of motion that are valid along Birkhoffian equations extremals were obtained. This theorem provides an explicit algorithmic way to compute a constant for any Birkhoffian systems. It overcomes some defects of existing methods for studying the conserved quantities of fractional order dynamical systems. Finally, two corollaries were given.