Which is correct?
I congratulated him for coming first in the race.
I congratulated him on coming first in the race.
In common mistakes in English by T.j.Fitikides (Longman) is written congratulate on not for and didn't say anything why on not for. Ex: Don't say: I congratulate you for your success. Say: I congratulate you on your success. (Common Mistakes in English)
According to Oxford Dictionaries Online the verb congratulate collocates with both prepositions, but the meaning is slightly different.
When you congratulate someone on something you give them your good wishes because something special or pleasant has happened to them, e.g. "I'd like to congratulate you on your marriage".
When you congratulate someone for something you praise them for an achievement, e.g. "I'd like to congratulate the staff for their good job".
According to Google NGram Viewer congratulate on is a lot more frequent than congratulate for, but the latter is used nevertheless.
To answer your question, both sound natural to me.