לרפואת אסתר רות בת נעמי שרה בתוך שח"י
We say in davening שירה חדשה שבחו גאולים - [At Kriyas Yam Suf] the redeemed sang a new song. There is an emphasis on the fact that it was new. Moshe Rabbeinu knew that a miracle was to occur, nevertheless when it happened it says אז ישיר which Rashi explains to mean עלה בלבו שישיר - He thought to sing. Which means that even though he may well have thought to sing before the miracle, once it happened there was a התחדשות - this renewed appreciation of the great acts of Hashem which caused the Jews to sing this new song. [עי' ס' ואני תפילה עמי' י"ט]
In the same vein we can understand the pasuk ואני בחסדך בטחתי יגל לבי בישועתך אשירה לה' כי גמל עלי - I was SURE of your chesed, I will rejoice in your salvation, I will sing to Hashem because he has bestowed it upon me. Meaning - I knew all along that Hashem was going to save me but when it actually happened I sang with renewed joy. Experiencing the salvation can't be compared to merely believing in it.
