Det område, som i dag er Ulstrup, var indtil midten af 1800-tallet landbrugsjord.
Ved anlæggelse af Langå-Viborgbanen blev der etableret en station i 1863 på herregården Ulstrups marker. I 1870’erne blev der bygget en bro over Gudenå til vejen mellem Randers og Silkeborg, og Ulstrup blev herefter et trafikknudepunkt. Der opstod i de følgende årtier en stationsby syd for Gudenå med markedsplads, handel, håndværk og industri.
Byen fortsatte med at udvikle sig op gennem 1900-tallet. I 1921 var der 454 indbyggere i Ulstrup, og dette tal voksede til 990 personer i 1960. Indbyggerne levede af håndværk og industri, handel og liberale erhverv. Opførelsen af en kirke i den voksende by påbegyndtes i 1952 og foregik i etaper. Derudover fik Ulstrup centralskole og ungdomsskole samt bibliotek. Der kom også fabrikker, bank- og sparekassefilialer samt hotel.
I 1970 blev Ulstrup en del af Hvorslev Kommune, hvor byen blev kommunens største. I 1970 havde Ulstrup 1.196 indbyggere, og befolkningstallet nåede i 2006 op på 2.001 personer.