Theorem 1 in http://www.zbmath.org/?q=an:00912201 (J. Loss On the conjugacy problem for automorphisms of free groups. Topology 35, n.3 p779-806, 1996) 
states

"The conjugacy problem for outer automorphisms of a free group admits a solution."