Lokomotiv was founded in 2002. In 2002–2003 club played in second level of Uzbek Football – First League and from 2004—2010 in Uzbek League. In the 2009 season Lokomotiv, led by Vadim Abramov reached 6th position in league.
In June 2012 Khoren Oganesian left the club after his contract expired and Ravshan Muqimov was appointed as coach. At the end of the 2012 season the club finished 3rd after Pakhtakor Tashkent and Bunyodkor. This was the club's 2nd best performance in the league and qualified to play in the 2013 AFC Champions League for the first time. In the 2013 AFC Champions League qualifying play-off round Lokomotiv played against Al Nasr based in Dubai but Lokomotiv lost 3–2 and failed to qualify for the group stage of tournament.
In 2013 season Lokomotiv Tashkent finished 2nd after Bunyodkor for the first time in club's history and gained promotion to 2014 AFC Champions League play-off. On 9 February 2014 in 2014 AFC Champions League qualifying play-off round match in Tashkent against Al-Kuwait Lokomotiv lost with score 1:3 and finished its participation in the tournament. On 1 July 2014 in Uzbek Cup semifinal Lokomotiv overcame Pakhtakor in two leg competition by 3:2 and to play in Cup Final against Bunyodkor. In 2014 Cup Final match on 12 November 2014 in Olmaliq, Lokomotiv overcame Bunyodkor by 1:0 and won the trophy for the first time in its first Cup Final. The only goal scored in 106' midfielder Jasur Hasanov. In Uzbek League club finished 2014 season again as runners-up after Pakhtakor like the previous season.
On 8 March 2015, in Supercup match against Pakhtakor, Lokomotiv overcame by 4–0 and won its first SuperCup after a disappointing loss to Bunyodkor in 2014. In 2016 Lokomotiv made double by winning League and Uzbek Cup. Lokomotiv won 2016 League and became the champions for the first time in its history after three consequent seasons finishing as runners-up (2013-2015). In 2017 Lokomotiv made its second double, winning second champions title and Cup.
The shirt sponsor of Lokomotiv is the national rail carrier O'zbekiston Temir Yo'llari. Lokomotiv's shirts had been made by manufacturer Adidas until 2013. In February 2013, it was announced the club had signed a contract with Joma as the club's new kit manufacturer.
Had international caps for their respective countries or made significant contributions to the team in terms of appearances or goals. Players whose name is listed in bold are still playing for Lokomotiv.