This question is not a duplicate of Tannis Esther reason because it is not a question of the reason just about the time.
In Megilat Taanit it is mentioned that people should not fast on the day before Purim: https://he.wikipedia.org/wiki/מגילת_תענית
Furthermore as we can see here:
http://tora.us.fm/tnk1/ktuv/mgilot/tklt_avrhm_tanit.html
In Masechet Sofrim there is a citation:
שלושה ימי הצום אין מתעניין אותם רצופין אלא פרודין; שני וחמישי ושני. רבותינו שבארץ ישראל נהגו להתענות אחרי ימי הפורים מפני ניקנור וחביריו [2], ועוד שמאחרין בפורענות ואין מקדימין (מסכת סופרים פי״ז,ד).
It looks like the minhag was to fast after Purim and not before because of the victory of the Jews against Nicanor.
In the Talmud Bavli, there is no direct mention of this fast (יום קהילה לכל does not look for me as a real source, as far as this is just cited indirectly and furthermore just a valid source according to Rabenu Tam and not Rashi or the Rambam). So my question is when did we start to fast on 13th Addar.
The earliest source I am aware of is שאילתות דרב אחאי גאון but this is from the eight century, which is about 1300 years after the story of Purim. When did the custom start?