We analyse the complexity of constructing involution centralisers in unitary groups over fields of odd order. In particular, we prove logarithmic bounds on the number of random elements required to generate a subgroup of the centraliser of a strong involution that contains the last term of its derived series. We use this to strengthen previous bounds on the complexity of recognition algorithms for unitary groups in odd characteristic. Our approach generalises and extends two previous papers by the second author and collaborators on strong involutions and regular semisimple elements of linear groups.