Indian Railways has allocated the service number 12723 for the Hyderabad–New Delhi run, and service number 12724 for the New Delhi–Hyderabad run. The train service was first commissioned by Madhu Dandavate in 1976.
During 1978, the Andhra Pradesh Express covered the distance in just under 23 hours. Since then the running time of the service has increased. When this train was introduced many of the sections of the route were single-line. The signalling in 1978 was semaphore based.
When the service introduced, the 14-coach train was pulled by a 2600 HP ALCO derived diesel locomotive – a WDM2. In 1981 the capacity was increased to 21 coaches pulled by 2 ALCO (WDM2) derived locomotives with a combined 5200 HP. The train originally had a fully equipped pantry car.
Currently the train operates with 24 coaches (including 7 air conditioned coaches) and is pulled by electric locomotives (WAP-7 / WAP4) throughout.
From its commissioning in 1978 until the early 1990s there were just five stops for Andhra Pradesh Express service – Jhansi Junction, Bhopal Junction, Nagpur, Balharshah and Kazipet. Since then several intermediate stops have been added leading to the present run time of around 27 hours.
After the bifurcation of Andhra Pradesh, Andhra Pradesh Express runs from Telangana and hence, the name of the train will be renamed soon to Telangana Express. The new train between Vijayawada-Delhi will be named as AP Express.