 FAIR: Maximus is a general in the professional roman army (SPQR),  but as he is Spanish and not a Roman by birth he would be in the  Auxilia. However, you did not need to be a native Roman to serve in  the legions, only a Roman citizen. Since Spain was a Roman province  at the time the movie is set, it is very likely that Maximus was a  Roman citizen in addition to being a native of Spain.