Andrew Harlan war ein Cousin des Kongressabgeordneten Aaron Harlan (1802–1868) aus Ohio. Er besuchte die öffentlichen Schulen seiner Heimat. Nach einem anschließenden Jurastudium und seiner im Jahr 1839 erfolgten Zulassung als Rechtsanwalt begann er in Richmond (Indiana) in diesem Beruf zu arbeiten. Noch im gleichen Jahr zog er nach Marion. Im Jahr 1842 wurde er Verwaltungsangestellter beim Repräsentantenhaus von Indiana.
Politisch war Harlan damals Mitglied der Demokratischen Partei. Zwischen 1846 und 1848 saß er als Abgeordneter im Repräsentantenhaus von Indiana. Bei den Kongresswahlen des Jahres 1848 wurde er im zehnten Wahlbezirk seines Staates in das US-Repräsentantenhaus in Washington, D.C. gewählt, wo er am 4. März 1849 die Nachfolge von William Rockhill antrat. Bis zum 3. März 1851 konnte er zunächst eine Legislaturperiode im Kongress absolvieren. Im Jahr 1852 wurde er im damals neugeschaffenen elften Distrikt von Indiana erneut in den Kongress gewählt, wo er zwischen dem 4. März 1853 und dem 3. März 1855 eine weitere Amtszeit verbringen konnte. Während dieser Zeit war er Vorsitzender des Committee on Mileage. Da er sich gegen die Rücknahme des Missouri-Kompromisses aussprach, wurde er aus seiner Partei ausgeschlossen.
Im Jahr 1854 lehnte Harlan eine Nominierung zur Wiederwahl als Kandidat der kurzlebigen People’s Party ab. Anschließend wurde er Mitglied der neugegründeten Republikanischen Partei. Im Jahr 1861 zog er in das Dakota-Territorium; dort wurde er Mitglied und Präsident des territorialen Repräsentantenhauses. Im September 1862 wurde er während eines Indianeraufstandes von den Indianern aus Dakota vertrieben. Anschließend ließ er sich in Savannah (Missouri) nieder, wo er wieder als Anwalt praktizierte. Zwischen 1864 und 1868 war Harlan Abgeordneter im Repräsentantenhaus von Missouri, als dessen Präsident er seit 1866 fungierte. Anschließend zog er nach Wakeeney in Kansas. Dort arbeitete er als Jurist. Zwischen 1890 und 1894 war er dort auch Posthalter. Danach kehrte er nach Savannah zurück, wo er am 19. Mai 1907 verstarb.
