アトランタ-ホークスとペイサーズ復帰
2004年オフにアトランタ-ホークスに移籍。アントワン-ウォーカーと共にチーム再建の中心選手となる。 その年アトランタは最下位の成績に沈むが、ジョシュ-スミスやジョシュ-チルドレスなど、有望な若手をそろえ、将来を賭けることになった。ハリントン自身もキャリアアベレージを更新した。2005-2006シーズン開幕前、アトランタはフェニックス-サンズからジョー-ジョンソンを大型契約でバスケットシューズ 得。ハリントンとの2枚看板を張った。しかしながら、わずかに23勝しか挙げられなかった。
2006年8月、トレードで古巣であるインディアナに復帰した。かねてから移籍が規定路線だったが、なかなか移籍先が決まらず、8月下旬になってようやく決定した。ドアマットチームであるアトランタでの選手生活は、決して満足できるものではなかったと、複雑な胸中を明かした。
ゴールデンステート-ウォリアーズ
2006-07シーズン途中の1月17日、トレードによりマイク-ダンリービー-Jr、トロイ-マーフィー、アイク-ディオグ、キース-マクリオドと交換で、スティーブン-ジャクソン、サルナス-ヤシケヴィシウス、ジョシュ-パウエルと共にウォリアーズへ移籍した。古巣ですごしたシーズンは1シーズン続かなかった。 ウォリアーズはNBA一のランアンドガンオフェンスを敷くチームであり、ビッグマンでありながらアウトサイドシュートが得意なハリントンは戦術にフィットし中心選手の1人となった。