  Algebraic properties of the BRST symmetry associated to the twisted gauge
symmetry occurring in the $\kappa$-Poincar\'e invariant gauge theories on the
$\kappa$-Minkowski space are investigated. We find that the BRST operation
associated to the gauge invariance of the action functional can be continuously
deformed together with its corresponding Leibniz rule, into a nilpotent twisted
BRST operation, leading to a twisted BRST symmetry algebra which may be viewed
as a noncommutative analog of the usual Yang-Mills BRST algebra.
