Der Ort geht auf die 1894 eröffnete Bahnstation Kotschubajewo zurück, die 1905 in Moskalenki umbenannt wurde. Um diese Station entstand wenig später die Ortschaft Olgino. Diese erhielt 1958 den Status einer Siedlung städtischen Typs. 1969 wurde der Name an die Bezeichnung der Bahnstation angepasst.
In der Umgebung von Moskalenki befanden sich ehemals zahlreiche Ansiedlungen überwiegend deutschsprachiger Russlandmennoniten, die schon zu Beginn des 20. Jahrhunderts aus der heutigen Ukraine dorthin ausgewandert sind. Ihre Umgangssprache Plautdietsch, ein niederdeutscher Dialekt namens Niederpreußisch, ist dort bis heute erhalten geblieben.
↑Itogi Vserossijskoj perepisi naselenija 2010 goda. Tom 1. Čislennostʹ i razmeščenie naselenija (Ergebnisse der allrussischen Volkszählung 2010. Band 1. Anzahl und Verteilung der Bevölkerung). Tabellen 5, S. 12–209; 11, S. 312–979 (Download von der Website des Föderalen Dienstes für staatliche Statistik der Russischen Föderation)